hdu1312 参考答案

   1 /*
   2 hdu 1312 经典：二维BFS
   3 ymc 2008/09/18
   4 题目大意：
   5 在一块矩形地面上铺着n×m的瓷砖，瓷砖有红色与黑色。
   6 .代表黑色，#代表红色，@为初始人所站立的黑色瓷砖位置。
   7 人每次可以移动的相邻的黑色瓷砖上，问可达的黑色瓷砖总共
   8 有多少块。
   9 分析与解题思路：
  10 经典BFS
  11 */
  12 #include <iostream>
  13 #include <queue>
  14 using namespace std;
  15 const int N=25;
  16 char map[N][N];
  17 bool used[N][N];
  18 int n,m;
  19 int sx,sy;
  20 int step[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
  21 bool Init()
  22 {
  23     scanf("%d %d",&m,&n);
  24     if(n==0&&m==0)
  25         return 0;
  26     for(int i=0;i<n;i++)
  27     {
  28         scanf("%s",map[i]);
  29         for(int j=0;j<m;j++)
  30             if(map[i][j]=='@')
  31             {
  32                     sx=i;
  33                     sy=j;
  34             }
  35     }
  36     return 1;
  37 }
  38 int BFS()
  39 {
  40     int ans=1;
  41     queue<int> q;
  42     memset(used,0,sizeof(used));
  43     q.push(sx);
  44     q.push(sy);
  45     used[sx][sy]=true;
  46     int x,y;
  47     int x1,y1;
  48     while(!q.empty())
  49     {
  50         x=q.front();q.pop();
  51         y=q.front();q.pop();
  52         for(int k=0;k<4;k++)
  53         {
  54             x1=x+step[k][0];
  55             y1=y+step[k][1];
  56             if(x1<0||x1>=n||y1<0||y1>=m)
  57                 continue;
  58             if(used[x1][y1]||map[x1][y1]=='#')
  59                 continue;
  60             used[x1][y1]=true;
  61             q.push(x1),q.push(y1);
  62             ans++;
  63         }
  64     }
  65     return ans;
  66 }
  67 int main()
  68 {
  69     int ans;
  70     while(Init())
  71     {
  72         ans=BFS();
  73         printf("%d\n",ans);
  74     }
  75 }