#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MN = 456;
int N, M;
char G[MN][MN];
priority_queue<pii> pq;
int dist[MN * MN * 2], cnt1[MN * MN * 2], cnt2[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 < N; i++) for(int j = 0; j < M; j++) for(int k = 0; k < 2; k++) dist[ f(i, j, k) ] = cnt1[ f(i, j, k) ] = cnt2[ f(i, j, k) ] = 1e9;
for(int i = 0; i < M; i++) {
cnt1[ f(0, i, 1) ] = 0;
cnt1[ f(N - 1, i, 0) ] = 0;
}
for(int i = 0; i < N; i++) {
cnt2[ f(i, 0, G[i][0] == 'Z') ] = 0;
cnt2[ f(i, M - 1, G[i][M - 1] == 'N') ] = 0;
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
for(int k = 0; k < 2; k++) {
if(cnt1[ f(i, j, k) ] != 1e9 && cnt2[ f(i, j, k) ] != 1e9) {
dist[ f(i, j, k) ] = 1;
pq.push({ -1, f(i, j, k) });
//cout << i << ' ' << j << ' ' << k << endl;
}
}
}
}
while(!pq.empty()) {
int u = pq.top().second;;
int ud = -pq.top().first;
pq.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[u] < ud) continue;
if(dist[ f(r, c, t ^ 1) ] > dist[u] + 1) {
dist[ f(r, c, t ^ 1) ] = dist[u] + 1;
pq.push({ -dist[ f(r, c, t ^ 1) ], f(r, c, t ^ 1) });
}
if(t) {
int nr = r - 1;
int nc = c;
if(0 <= nr) {
cnt1[ f(nr, nc, 0) ] = min(cnt1[ f(nr, nc, 0) ], dist[u]);
int tmp = cnt1[ f(nr, nc, 0) ] + cnt2[ f(nr, nc, 0) ];
if(dist[ f(nr, nc, 0) ] > tmp + 1) {
dist[ f(nr, nc, 0) ] = dist[u] + 1;
pq.push({ -dist[ f(nr, nc, 0) ], f(nr, nc, 0) });
}
}
}
else {
int nr = r + 1;
int nc = c;
if(nr < N) {
cnt1[ f(nr, nc, 1) ] = min(cnt1[ f(nr, nc, 1) ], dist[u]);
int tmp = cnt1[ f(nr, nc, 1) ] + cnt2[ f(nr, nc, 1) ];
if(dist[ f(nr, nc, 1) ] > tmp + 1) {
dist[ f(nr, nc, 1) ] = dist[u] + 1;
pq.push({ -dist[ f(nr, nc, 1) ], f(nr, nc, 1) });
}
}
}
if(t ^ (G[r][c] == 'N')) {
int nr = r;
int nc = c - 1;
if(0 <= nc) {
cnt2[ f(nr, nc, G[nr][nc] == 'N') ] = min(cnt2[ f(nr, nc, G[nr][nc] == 'N') ], dist[u]);
int tmp = cnt1[ f(nr, nc, G[nr][nc] == 'N') ] + cnt2[ f(nr, nc, G[nr][nc] == 'N') ];
if(dist[ f(nr, nc, G[nr][nc] == 'N') ] > tmp + 1) {
dist[ f(nr, nc, G[nr][nc] == 'N') ] = dist[u] + 1;
pq.push({ -dist[ f(nr, nc, G[nr][nc] == 'N') ], f(nr, nc, G[nr][nc] == 'N') });
}
}
}
else {
int nr = r;
int nc = c + 1;
if(nc < M) {
cnt2[ f(nr, nc, G[nr][nc] == 'Z') ] = min(cnt2[ f(nr, nc, G[nr][nc] == 'N') ], dist[u]);
int tmp = cnt1[ f(nr, nc, G[nr][nc] == 'Z') ] + cnt2[ f(nr, nc, G[nr][nc] == 'Z') ];
if(dist[ f(nr, nc, G[nr][nc] == 'Z') ] > tmp + 1) {
dist[ f(nr, nc, G[nr][nc] == 'Z') ] = dist[u] + 1;
pq.push({ -dist[ f(nr, nc, G[nr][nc] == 'Z') ], 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) ] != 1e9 && dist[ f(i, j, 1) ] != 1e9) 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:18: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:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n");
~~~~~^~~~~~
sandwich.cpp:23: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 |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
412 KB |
Output is correct |
| 4 |
Correct |
3 ms |
412 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
416 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 |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
412 KB |
Output is correct |
| 4 |
Correct |
3 ms |
412 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
416 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
