#include<bits/stdc++.h>
using namespace std;
const int MN = 456;
int N, M;
char G[MN][MN];
queue<int> q;
int dist[MN * MN * 2], cnt[MN * MN * 2];
int f(int r, int c, int t) {
return r * (2 * M) + c * 2 + t;
}
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 < M; i++) {
cnt[ f(0, i, 1) ]++;
cnt[ f(N - 1, i, 0) ]++;
}
for(int i = 0; i < N; i++) {
cnt[ f(i, 0, G[i][0] == 'Z') ]++;
cnt[ f(i, M - 1, G[i][M - 1] == 'N') ]++;
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
for(int k = 0; k < 2; k++) {
if(cnt[ f(i, j, k) ] == 2) {
dist[ f(i, j, k) ] = 1;
q.push(f(i, j, k));
//cout << i << ' ' << j << ' ' << k << endl;
}
}
}
}
while(!q.empty()) {
int u = q.front(); q.pop();
int r = u / (2 * M);
int c = (u % (2 * M)) / 2;
int t = u % 2;
//cout << r << ' ' << c << ' ' << t << ' ' << dist[u] << endl;
if(!dist[ f(r, c, t ^ 1) ]) {
dist[ f(r, c, t ^ 1) ] = dist[u] + 1;
q.push(f(r, c, t ^ 1));
}
if(t) {
int nr = r - 1;
int nc = c;
if(0 <= nr && !dist[ f(nr, nc, 0) ]) {
cnt[ f(nr, nc, 0) ]++;
if(cnt[ f(nr, nc, 0) ] == 2) {
dist[ f(nr, nc, 0) ] = dist[u] + 1;
q.push(f(nr, nc, 0));
}
}
}
else {
int nr = r + 1;
int nc = c;
if(nr < N && !dist[ f(nr, nc, 1) ]) {
cnt[ f(nr, nc, 1) ]++;
if(cnt[ f(nr, nc, 1) ] == 2) {
dist[ f(nr, nc, 1) ] = dist[u] + 1;
q.push(f(nr, nc, 1));
}
}
}
if(t ^ (G[r][c] == 'N')) {
int nr = r;
int nc = c - 1;
if(0 <= nc && !dist[ f(nr, nc, G[nr][nc] == 'N') ]) {
cnt[ f(nr, nc, G[nr][nc] == 'N') ]++;
if(cnt[ f(nr, nc, G[nr][nc] == 'N') ] == 2) {
dist[ f(nr, nc, G[nr][nc] == 'N') ] = dist[u] + 1;
q.push(f(nr, nc, G[nr][nc] == 'N'));
}
}
}
else {
int nr = r;
int nc = c + 1;
if(nc < M && !dist[ f(nr, nc, G[nr][nc] == 'Z') ]) {
cnt[ f(nr, nc, G[nr][nc] == 'Z') ]++;
if(cnt[ f(nr, nc, G[nr][nc] == 'Z') ] == 2) {
dist[ f(nr, nc, G[nr][nc] == 'Z') ] = dist[u] + 1;
q.push(f(nr, nc, G[nr][nc] == 'Z'));
}
}
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(dist[ f(i, j, 0) ] && dist[ f(i, j, 1) ]) printf("%d ", min(dist[ f(i, j, 0) ], dist[ f(i, j, 1) ]) + 1);
else printf("-1 ");
}
printf("\n");
}
}
Compilation message
sandwich.cpp: In function 'int main()':
sandwich.cpp:16: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:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n");
~~~~~^~~~~~
sandwich.cpp:21: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 |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
416 KB |
Output is correct |
4 |
Correct |
3 ms |
568 KB |
Output is correct |
5 |
Incorrect |
3 ms |
648 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
416 KB |
Output is correct |
4 |
Correct |
3 ms |
568 KB |
Output is correct |
5 |
Incorrect |
3 ms |
648 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |