hdu1241 参考答案

   1 /*
   2 hdu 1241 经典：BFS
   3 ymc 2008/09/16
   4 题目大意：
   5 有n×m的地图上，@代表石油，.代表没有石油，
   6 相邻的@表示石油属于同一个石油，求总共有多少块石油。
   7 注意：相邻表示连个格子水平，垂直或者对角相邻。
   8 分析与解题思路：
   9 每次先查找一个没有匹配过的@,然后用BFS查找所有与@匹配
  10 的其它@。
  11 */
  12 #include <iostream>
  13 #include <queue>
  14 using namespace std;
  15 const int N=110;
  16 char map[N][N];
  17 bool used[N][N];
  18 int n,m;
  19 int step[8][2]={{1,0},{-1,0},{0,1},{0,-1},
  20                 {1,1},{1,-1},{-1,1},{-1,-1}};
  21 
  22 int Init()
  23 {
  24     scanf("%d %d",&n,&m);
  25     if(n==0&&m==0)
  26         return 0;
  27     memset(map,'*',sizeof(map));
  28     memset(used,0,sizeof(used));
  29     for(int i=0;i<n;i++)
  30         scanf("%s",map[i]);
  31     return 1;
  32 }
  33 bool Find(int &x,int &y)//搜索未匹配的@
  34 {
  35     for(int i=0;i<n;i++)
  36     {
  37         for(int j=0;j<m;j++)
  38         {
  39             if(!used[i][j]&&map[i][j]=='@')
  40             {
  41                 x=i;
  42                 y=j;
  43                 return true;
  44             }
  45         }
  46     }
  47     return false;
  48 }
  49 void BFS(int x,int y)//所有与(x,y)的@属于同一块石油的@匹配
  50 {
  51     queue<int> q;
  52     used[x][y]=true;
  53     q.push(x);
  54     q.push(y);
  55     int x1,y1,x2,y2;
  56     while(!q.empty())
  57     {
  58         x1=q.front();q.pop();
  59         y1=q.front();q.pop();
  60         for(int k=0;k<8;k++)
  61         {
  62             x2=x1+step[k][0];
  63             y2=y1+step[k][1];
  64             if(x2<0||x2>=n||y2<0||y2>=m)
  65                 continue;
  66             if(map[x2][y2]=='*'||used[x2][y2]==true)
  67                 continue;
  68             used[x2][y2]=true;
  69             q.push(x2);
  70             q.push(y2);
  71         }
  72     }
  73 }
  74 int main()
  75 {
  76     int x,y;
  77     int ans;
  78     while(Init())
  79     {
  80         ans=0;
  81         while(Find(x,y))
  82         {
  83             BFS(x,y);
  84             ans++;
  85         }
  86         printf("%d\n",ans);
  87     }
  88 }