#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MN = 444;
int N, M;
char G[MN][MN];
vector<int> adj[MN * MN * 2];
int f(int r, int c, int up) {
return 2 * (r * M + c) + up;
}
int tin[MN * MN * 2], tout[MN], timer, cnt;
int ans[MN * MN * 2];
void dfs(int u) {
tin[u] = timer++;
cnt++;
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if(tin[v] != -1) {
if(tin[v] < tin[u] && tout[v] == -1) cnt = 1e9;
continue;
}
dfs(v);
}
tout[u] = timer;
}
int main() {
scanf("%d %d", &N, &M);
for(int i = 0; i < N; i++) {
scanf("\n");
for(int j = 0; j < M; j++) {
scanf("%c", &G[i][j]);
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(G[i][j] == 'N') {
if(i) adj[ f(i, j, 1) ].push_back(f(i - 1, j, 1));
if(j < M - 1) adj[ f(i, j, 1) ].push_back(f(i, j + 1, G[i][j + 1] == 'N'));
if(i < N - 1) adj[ f(i, j, 0) ].push_back(f(i + 1, j, 0));
if(j) adj[ f(i, j, 0) ].push_back(f(i, j - 1, G[i][j - 1] == 'Z'));
}
if(G[i][j] == 'Z') {
if(i) adj[ f(i, j, 1) ].push_back(f(i - 1, j, 1));
if(j) adj[ f(i, j, 1) ].push_back(f(i, j - 1, G[i][j - 1] == 'Z'));
if(i < N - 1) adj[ f(i, j, 0) ].push_back(f(i + 1, j, 0));
if(j < M - 1) adj[ f(i, j, 0) ].push_back(f(i, j + 1, G[i][j + 1] == 'N'));
}
}
}
for(int i = 0; i < M; i++) {
memset(tin, -1, sizeof(tin));
memset(tout, -1, sizeof(tout));
timer = 0;
cnt = 0;
for(int j = 0; j < N; j++) {
if(tin[ f(j, i, 1) ] == -1) dfs(f(j, i, 1));
ans[ f(j, i, 1) ] = cnt;
}
memset(tin, -1, sizeof(tin));
memset(tout, -1, sizeof(tout));
timer = 0;
cnt = 0;
for(int j = N - 1; j >= 0; j--) {
if(tin[ f(j, i, 0) ] == -1) dfs(f(j, i, 0));
ans[ f(j, i, 0) ] = cnt;
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(min(ans[ f(i, j, 0) ], ans[ f(i, j, 1) ]) >= 1e9) printf("-1 ");
else printf("%d ", 2 * min(ans[ f(i, j, 0) ], ans[ f(i, j, 1) ]));
}
printf("\n");
}
}
Compilation message
sandwich.cpp: In function 'void dfs(int)':
sandwich.cpp:24:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
sandwich.cpp: In function 'int main()':
sandwich.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~
sandwich.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n");
~~~~~^~~~~~
sandwich.cpp:43:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c", &G[i][j]);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
11128 KB |
Output is correct |
| 2 |
Correct |
19 ms |
11128 KB |
Output is correct |
| 3 |
Correct |
12 ms |
11128 KB |
Output is correct |
| 4 |
Correct |
12 ms |
11128 KB |
Output is correct |
| 5 |
Correct |
12 ms |
11128 KB |
Output is correct |
| 6 |
Correct |
31 ms |
11384 KB |
Output is correct |
| 7 |
Incorrect |
24 ms |
11384 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
11128 KB |
Output is correct |
| 2 |
Correct |
19 ms |
11128 KB |
Output is correct |
| 3 |
Correct |
12 ms |
11128 KB |
Output is correct |
| 4 |
Correct |
12 ms |
11128 KB |
Output is correct |
| 5 |
Correct |
12 ms |
11128 KB |
Output is correct |
| 6 |
Correct |
31 ms |
11384 KB |
Output is correct |
| 7 |
Incorrect |
24 ms |
11384 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
