一道搜索题。
这个关键就是搜索起始点的问题。
关键数据。
10 10 0 0 0 0 0 0 0 0 0 0 0 1 5 6 5 1 2 3 4 0 0 1 2 3 0 0 0 0 0 0 0 1 4 5 0 1 1 1 2 3 0 1 0 0 0 1 1 2 2 3 0 1 0 1 2 1 2 3 4 5 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 4 0 0 0 0 0 2 0 2 0 0 0
一个巧妙的处理方法就是将四周全部设为1 这样相当于强加了一个边框。。。
#include<stdio.h> #include<string.h> #include<queue> using namespace std; int divs[4][2]= {{1,0},{0,1},{-1,0},{0,-1}}; int mp[1000][1500]; int n,m; struct node { int x,y; }; void bfs(int a,int b) { queue<node> Q; node p,q; p.x=a; p.y=b; Q.push(p); mp[a][b]=0; while(!Q.empty()) { p=Q.front(); Q.pop(); for(int i=0; i<4; i++) { q.x=p.x+divs[i][0]; q.y=p.y+divs[i][1]; if(q.x>=0&&q.x<=n+1&&q.y>=0&&q.y<=m+1&&mp[q.x][q.y]>0) { mp[q.x][q.y]=0; Q.push(q); } } } } int main() { //freopen("a.txt","r",stdin); int t; scanf("%d",&t); while(t--) { scanf("%d%d",&m,&n); for(int i=0; i<=n+1; i++) for(int j=0; j<=m+1; j++) mp[i][j]=1; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d",&mp[i][j]); bfs(0,0); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(j-1) printf(" "); printf("%d",mp[i][j]); } printf("\n"); } } return 0; }