이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
int dir[200002], bit[16];
bool visited[802][802];
int pos[802][802], U[802][802];
int M, R, C;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int cnt = 0;
void init()
{
cnt = 0;
for(int i=1;i<=R;i++) for(int j=1;j<=C;j++)
{
pos[i][j] = 0;
visited[i][j] = false;
}
}
void dfs(int x, int y)
{
visited[x][y] = true;
cnt++;
for(int d=0;d<4;d++)
{
int nx = x + dx[d];
int ny = y + dy[d];
if(nx < 1 || nx > R || ny < 1 || ny > C || U[nx][ny] == 0 || visited[nx][ny]) continue;
pos[nx][ny] += (1<<d);
if(U[nx][ny] <= bit[pos[nx][ny]]) dfs(nx, ny);
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> M >> R >> C;
string D; cin >> D;
for(int i=0;i<16;i++)
{
for(int j=0;j<2*M;j++) dir[j] = 0;
for(int j=0;j<M;j++)
{
if(D[j] == 'N' && (i & 1)) dir[j] = dir[j+M] = 1;
if(D[j] == 'S' && (i & 2)) dir[j] = dir[j+M] = 1;
if(D[j] == 'W' && (i & 4)) dir[j] = dir[j+M] = 1;
if(D[j] == 'E' && (i & 8)) dir[j] = dir[j+M] = 1;
}
int now = 0;
bit[i] = 0;
for(int j=0;j<2*M;j++)
{
if(dir[j] == 1) now++;
else now = 0;
bit[i] = max(bit[i], now);
}
if(now == 2 * M);
bit[i] = 300000;
}
for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) cin >> U[i][j];
int ans = R * C + 1;
int ansN = 1;
for(int i=1;i<=R;i++) for(int j=1;j<=C;j++)
{
if(U[i][j] == 0) continue;
init();
dfs(i, j);
if(cnt == ans) ansN++;
else if(cnt < ans)
{
ans = cnt;
ansN = 1;
}
}
cout << ans << "\n" << ansN << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |