UVA657 The die is cast（DFS、BFS）

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=598

这题题意看了老半天让求图形中的X的区域块数每个区域有多少个X是不相连的 DFS搜有多少个区域 BFS标记有每个区域里多少X区域块

注意两点吧 WA了5次第一个可能为X 就直接BFS 再DFS

第二 BFS中遇到的*要保留起来把相连的X标记完之后继续搜不然区域块数会被分开

View Code

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<string.h>
  4 #include<algorithm>
  5 void dfs(int x,int y);
  6 char c[51][51];
  7 int f[51][51],a[4][2] = {{1,0},{0,1},{-1,0},{0,-1}},num,n,m,tx,ty;
  8 using namespace std;
  9 int judge(int x,int y)
 10 {
 11     if(x<1||y<1||x>n||y>m)
 12     return 0;
 13     if(c[x][y]=='.')
 14     return 0;
 15     return 1;
 16 }
 17 
 18 void bfs(int x,int y)
 19 {
 20     int d = 1,p = 0,q[3000][2],i,flag = 0,aa[1000][2],g = 1;
 21     q[1][0] = x;
 22     q[1][1] = y;
 23     f[x][y] = 1;
 24     while(p!=d)
 25     {
 26         p++;
 27         for(i = 0 ; i < 4 ; i++)
 28         {
 29             int px = q[p][0]+a[i][0];
 30             int py = q[p][1]+a[i][1];
 31             if(judge(px,py)&&!f[px][py])
 32             {
 33                 if(c[px][py]=='X')
 34                 {
 35                     f[px][py] = 1;
 36                     q[++d][0] = px;
 37                     q[d][1] = py;
 38                 }
 39                 else
 40                 {
 41                     g++;
 42                     aa[g][0] = px;
 43                     aa[g][1] = py;
 44                 }
 45             }
 46         }
 47     }
 48     for(i = 1; i <= g; i++)
 49     dfs(aa[i][0],aa[i][1]);
 50 }
 51 void dfs(int x,int y)
 52 {
 53     int i,j,k;
 54     for(i = 0 ; i < 4 ; i++)
 55     {
 56         int px = x+a[i][0];
 57         int py = y+a[i][1];
 58         if(judge(px,py))
 59         {
 60             if(!f[px][py])
 61             {
 62                 if(c[px][py]=='*')
 63                 {
 64                     f[px][py] = 1;
 65                     dfs(px,py);
 66                 }
 67                 else
 68                 {
 69                     num++;
 70                     bfs(px,py);
 71                 }
 72             }
 73         }
 74     }
 75 
 76 }
 77 int main()
 78 {
 79     int i,j,k = 0,t,to[3000];
 80     while(scanf("%d %d",&m,&n)!=EOF)
 81     {
 82         if(n==0&&m==0)
 83         break;
 84         k++;
 85         memset(f,0,sizeof(f));
 86         for(i = 1; i <= n; i++)
 87         {
 88             getchar();
 89             for(j = 1; j <= m ; j++)
 90             {
 91                 c[i][j] = getchar();
 92             }
 93         }
 94         int g = 0;
 95         for(i = 1; i <= n ; i++)
 96         for(j = 1; j <= m ; j++)
 97         if(!f[i][j]&&(c[i][j] == '*'||c[i][j]=='X'))
 98         {
 99             f[i][j] = 1;
100             num = 0;
101             if(c[i][j] == 'X')
102             {
103                 num = 1;
104                 bfs(i,j);
105             }
106             dfs(i,j);
107             if(num>0&&num<7)
108             to[g++] = num;
109         }
110         sort(to,to+g);
111         printf("Throw %d\n",k);
112         for(i = 0 ; i < g ; i++)
113         {
114             if(i!=0)
115             printf(" ");
116             printf("%d",to[i]);
117         }
118         puts("");
119         puts("");
120     }
121     return 0;
122 }

附组数据

6 6

...XX*

.....X

...XX.

.....X

..XX..

....*X

Throw 1

1 1 1 1 2

6 6

...XX*

.....X

...XX*

.....X

...X**

.....X

Throw 2