提交时间:2025-06-08 14:46:34

运行 ID: 37983

#include <bits/stdc++.h> using namespace std; int n,sy,ey,E[1010][1010][4],nxt[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; int vis[1010][1010],dep[1010][1010],px[1000010],py[1000010],step,ans[1010][1010]; bool dfs(int x,int y) { step++; px[step] = x; py[step] = y; vis[x][y] = 1; if(x == n && y == ey) return 1; for(int i = 0;i < 4;i++) { if(!E[x][y][i]) continue; int tx = x + nxt[i][0],ty = y + nxt[i][1]; if(vis[tx][ty]) continue; bool fl = dfs(tx,ty); if(fl) return 1; } step--; vis[x][y] = 0; return false; } void calc(int x,int y,int depf,int depa) { for(int i = 0;i < 4;i++) { if(!E[x][y][i]) continue; int tx = x + nxt[i][0],ty = y + nxt[i][1]; if(vis[tx][ty]) continue; if(tx < depf) continue; vis[tx][ty] = 1; if(tx >= depa) ans[tx][ty] = 2; else ans[tx][ty] = 1; calc(tx,ty,depf,depa); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> sy >> ey; for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { int val; cin >> val; if(!val) E[i - 1][j][0] = 1,E[i][j][1] = 1; } } for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { int val; cin >> val; if(!val) E[i][j - 1][2] = 1,E[i][j][3] = 1; } } dfs(1,sy); int flow = n + 1,accum = n + 1; for(int i = step;i >= 1;i--) { int x = px[i],y = py[i]; flow = min(flow,x); if(i != step) dep[x][y] = min(dep[px[i + 1]][py[i + 1]],x); else dep[x][y] = x; ans[x][y] = 1; if(i != step && dep[x][y] < x) ans[x][y] = 2; if(ans[x][y] == 2) accum = min(accum,x); if(i == step) continue; if(px[i + 1] == px[i] + 1 && ans[x + 1][y] != 2) continue; calc(x,y,flow,min(accum,x + 1)); } for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) cout << ans[i][j] << " "; cout << "\n"; } return 0; }