提交时间:2025-06-08 14:04:10
运行 ID: 37972
#include<bits/stdc++.h> using namespace std; const int N=1000010; vector<int> v[N]; int n,st,ed,flag; int dep[N],son[N],fa[N],l[N],r[N],mk[N]; void add(int x,int y) { v[x].push_back(y); v[y].push_back(x); } void dfs(int x,int from) { mk[x]=1; if(x==ed) { flag=1; return ; } if(!mk[son[x]]) { flag=0; dfs(son[x],x); if(flag==0) mk[son[x]]=2; } if(!mk[l[x]]&&from!=l[x]) { flag=0; dfs(l[x],x); if(flag==0) mk[l[x]]=2; } if(!mk[r[x]]&&from!=r[x]) { flag=0; dfs(r[x],x); if(flag==0) mk[r[x]]=2; } if((mk[l[x]]==2||l[x]==from)&&(mk[r[x]]==2||r[x]==from)&&(mk[son[x]]==2||son[x]==from)&&fa[x]!=from) { mk[x]=2; dfs(fa[x],x); } if((mk[l[x]]==2||l[x]==from)&&(mk[r[x]]==2||r[x]==from)&&(mk[son[x]]==2||son[x]==from)&&(mk[fa[x]]==2||fa[x]==from)) mk[x]=2; } int main() { //freopen("maze.in","r",stdin); //freopen("maze.out","w",stdout); ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int x,y; cin>>n>>x>>y; st=x;ed=(n-1)*n+y; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>x; int now=(i-1)*n+j; if(x==0&&now-n>0) { //add(x,x-n); son[now-n]=now; fa[now]=now-n; } } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>x; int now=(i-1)*n+j; if(x==0) { //add(x,x-1); l[now]=now-1; r[now-1]=now; } } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dep[(i-1)*n+j]=i; mk[0]=2; dfs(st,0); mk[st]=1; //cout<<'\n'; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cout<<mk[(i-1)*n+j]<<" "; } cout<<'\n'; } }