#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct vertex{
int x, y;
bool z; ///up=1
vertex(){}
vertex(int _x, int _y, bool _z): x(_x), y(_y), z(_z) {}
};
struct node{
bool x[50][50];
int val;
}dp[50][50][2];
int deg[50][50][2], dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}, n, m;
int sb[50][50];
bool visited[50][50][2];
vector<string> matrix;
bool chk(int x, int y){
return (x>=0 && x<n && y>=0 && y<m);
}
void calc(vertex &V){
vertex x1, x2;
if (V.z) x1 = vertex(V.x+1, V.y, V.z);
else x1 = vertex(V.x-1, V.y, V.z);
if ((V.z && matrix[V.x][V.y]=='Z') || (!V.z && matrix[V.x][V.y]=='N')) x2 = vertex(V.x, V.y+1, V.z);
else x2 = vertex(V.x, V.y-1, V.z);
if (!chk(x1.x, x1.y)) swap(x1, x2);
x1.z = sb[x1.x][x1.y];
dp[V.x][V.y][V.z].val = dp[x1.x][x1.y][x1.z].val+1;
for (int i=0;i<n;i++){
for (int j=0;j<m;j++) dp[V.x][V.y][V.z].x[i][j] = dp[x1.x][x1.y][x1.z].x[i][j];
}
//if (V.x==1 && V.y==1 && V.z==1) printf(" %d %d %d\n %d %d %d\n", x1.x, x1.y, x1.z, x2.x, x2.)
if (!chk(x2.x, x2.y)) return;
x2.z = sb[x2.x][x2.y];
int cnt=0;
for (int i=0;i<n;i++){
for (int j=0;j<m;j++){
if (dp[V.x][V.y][V.z].x[i][j]&dp[x2.x][x2.y][x2.z].x[i][j]) cnt++;
dp[V.x][V.y][V.z].x[i][j] |= dp[x2.x][x2.y][x2.z].x[i][j];
}
}
dp[V.x][V.y][V.z].x[V.x][V.y] = 1;
dp[V.x][V.y][V.z].val += dp[x2.x][x2.y][x2.z].val-cnt;
}
int main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n >> m;
for (int i=0;i<n;i++){
string tmp;
cin >> tmp;
matrix.push_back(tmp);
}
for (int i=0;i<n;i++){
for (int j=0;j<m;j++) sb[i][j] = -1;
}
queue<vertex> q;
if (matrix[0][0]=='Z'){
q.push(vertex(0, 0, 0));
dp[0][0][0].val = 1;
dp[0][0][0].x[0][0] = 1;
sb[0][0] = 0;
}
if (matrix[0][m-1]=='N'){
q.push(vertex(0, m-1, 0));
dp[0][m-1][0].val = 1;
dp[0][m-1][0].x[0][m-1] = 1;
sb[0][m-1] = 0;
}
if (matrix[n-1][0]=='N'){
q.push(vertex(n-1, 0, 1));
dp[n-1][0][1].val = 1;
dp[n-1][0][1].x[n-1][0] = 1;
sb[n-1][0] = 1;
}
if (matrix[n-1][m-1]=='Z'){
q.push(vertex(n-1, m-1, 1));
dp[n-1][m-1][1].val = 1;
dp[n-1][m-1][1].x[n-1][m-1] = 1;
sb[n-1][m-1] = 1;
}
for (int i=0;i<n;i++){
for (int j=0;j<m;j++) deg[i][j][0] = deg[i][j][1] = 2;
}
for (int j=0;j<m;j++) deg[0][j][0]--, deg[n-1][j][1]--;
for (int i=0;i<n;i++){
if (matrix[i][0]=='Z') deg[i][0][0]--;
else deg[i][0][1]--;
if (matrix[i][m-1]=='N') deg[i][m-1][0]--;
else deg[i][m-1][1]--;
}
/*for (int i=0;i<n;i++){
for (int j=0;j<m;j++) printf("%d ", deg[i][j][0]);
printf("\n");
}
for (int i=0;i<n;i++){
for (int j=0;j<m;j++) printf("%d ", deg[i][j][1]);
printf("\n");
}*/
while(!q.empty()){
auto cur = q.front();
q.pop();
if (visited[cur.x][cur.y][cur.z]) continue;
visited[cur.x][cur.y][cur.z] = 1;
for (int k=0;k<4;k++){
vertex nxt = vertex(cur.x+dx[k], cur.y+dy[k], 0);
if (!chk(nxt.x, nxt.y)) continue;
if (k==1) nxt.z = 1;
else if (k==2 && matrix[nxt.x][nxt.y]=='N') nxt.z = 1;
else if (k==3 && matrix[nxt.x][nxt.y]=='Z') nxt.z = 1;
if (cur.z==sb[cur.x][cur.y])deg[nxt.x][nxt.y][nxt.z]--;
if (!deg[nxt.x][nxt.y][nxt.z]){
//printf(" %d %d %d: %d %d %d, %d\n", nxt.x, nxt.y, nxt.z, cur.x, cur.y, cur.z, sb[cur.x][cur.y]);
q.push(nxt);
calc(nxt);
if (sb[nxt.x][nxt.y]==-1) sb[nxt.x][nxt.y] = nxt.z;
}
}
}
/*
for (int i=0;i<n;i++){
for (int j=0;j<m;j++) printf("%d ", dp[i][j][0].val);
printf("\n");
}
for (int i=0;i<n;i++){
for (int j=0;j<m;j++) printf("%d ", dp[i][j][1].val);
printf("\n");
}
*/
for (int i=0;i<n;i++){
for (int j=0;j<m;j++){
int tmp1 = dp[i][j][0].val, tmp2 = dp[i][j][1].val;
if (!tmp1 && !tmp2) printf("-1 ");
else if (!tmp1) printf("%d ", tmp2*2);
else if (!tmp2) printf("%d ", tmp1*2);
else printf("%d ", min(tmp1, tmp2)*2);
}
printf("\n");
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
588 KB |
Output is correct |
| 3 |
Correct |
1 ms |
716 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
588 KB |
Output is correct |
| 3 |
Correct |
1 ms |
716 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
