用深搜因为要回溯 所以 超时了
1 2 #include<stdio.h> 3 #include<string.h> 4 #include<algorithm> 5 #include<math.h> 6 using namespace std; 7 int map[965][1445]; 8 int main() 9 { 10 void dfs(int i,int j); 11 int n,w,h,i,j; 12 scanf("%d",&n); 13 while(n--) 14 { 15 scanf("%d%d",&w,&h); 16 memset(map,0,sizeof(map)); 17 for(i=0;i<h;i++) 18 for(j=0;j<w;j++) 19 scanf("%d",&map[i][j]); 20 for(i=0;i<h;i++) 21 for(j=0;j<w;j++) 22 { 23 if(map[i][j]!=0&&(i==0||j==0||i==h-1||j==w-1)) 24 { 25 dfs(i,j); 26 break; 27 } 28 } 29 for(i=0;i<h;i++) 30 { 31 for(j=0;j<w-1;j++) 32 printf("%d ",map[i][j]); 33 printf("%d ",map[i][w-1]); 34 } 35 36 } 37 return 0; 38 } 39 void dfs(int i,int j) 40 { 41 if(map[i][j]!=0) 42 { 43 map[i][j]=0; 44 dfs(i+1,j); 45 dfs(i,j+1); 46 dfs(i-1,j); 47 dfs(i,j-1); 48 } 49 } 50
用广搜过了
1 2 #include<stdio.h> 3 #include<string.h> 4 #include<algorithm> 5 #include<math.h> 6 using namespace std; 7 int map[965][1445],p[1500000],w,h; 8 int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}; 9 int main() 10 { 11 void bfs(int i,int j); 12 int n,i,j,bx,by; 13 scanf("%d",&n); 14 while(n--) 15 { 16 scanf("%d%d",&w,&h); 17 memset(map,0,sizeof(map)); 18 for(i=0;i<h;i++) 19 for(j=0;j<w;j++) 20 scanf("%d",&map[i][j]); 21 for(i=0;i<h;i++) 22 for(j=0;j<w;j++) 23 if(map[i][j]!=0&&(i==0||j==0||i==h-1||j==w-1)) 24 bfs(i,j); 25 for(i=0;i<h;i++) 26 { 27 for(j=0;j<w-1;j++) 28 printf("%d ",map[i][j]); 29 printf("%d ",map[i][w-1]); 30 } 31 32 } 33 return 0; 34 } 35 void bfs(int i,int j) 36 { 37 int u,left=0,right=0,x,y; 38 u=i*w+j; 39 p[right++]=u; 40 map[u/w][u%w]=0; 41 while(left<right) 42 { 43 u=p[left++]; 44 x=u/w;y=u%w; 45 for(i=0;i<4;i++) 46 { 47 int nx=x+dx[i],ny=y+dy[i]; 48 if(map[nx][ny]!=0&&nx>=0&&nx<h&&ny>=0&&ny<w) 49 { 50 p[right++]=nx*w+ny; 51 map[nx][ny]=0; 52 } 53 } 54 } 55 } 56