哎,这道题从3月份学广搜开始就困扰我,做了2个月都没做对,一直拖到5月学动态规划,索性放下不管!
今天深搜一遍过……
主要思路:四个边缘进行搜索就可以了。
#include<bits/stdc++.h> using namespace std; int n,mp[35][35],dx[4]= {1,-1,0,0},dy[4]= {0,0,1,-1},u,v; void dfs(int x,int y) { mp[x][y]=-1; for(int i=0; i<4; i++) { u=x+dx[i],v=y+dy[i]; if(!mp[u][v])dfs(u,v); } } int main() { for(int i=0; i<35; i++) for(int j=0; j<35; j++) mp[i][j]=1; scanf("%d",&n); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d",&mp[i][j]); for(int i=1; i<=n; i++)if(!mp[1][i])dfs(1,i); for(int i=1; i<=n; i++)if(!mp[n][i])dfs(n,i); for(int i=1; i<=n; i++)if(!mp[i][1])dfs(i,1); for(int i=1; i<=n; i++)if(!mp[i][n])dfs(i,n); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { if(mp[i][j]==0)mp[i][j]=2; if(mp[i][j]==-1)mp[i][j]=0; } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) printf("%d ",mp[i][j]); cout<<endl; } return 0; }AC