hdu1198 参考答案

   1 /*
   2 zju 2412,hdu1198,并查集,BFS
   3 BFS或者DFS都可以
   4 ymc 2008/5/22
   5 题目大意：
   6 一个m×n的草地上，没一块草地上都有水管，水管的布局总共有11中情况。
   7 如果某一块草地上有水供应了，则和它有水管连接的草地都有水供应。
   8 使得所有草地都有水供应，至少要多少个水源。
   9 解题方法：
  10 搜索所有草地，如果当前没有的水供应，则加一个水源，用BFS或者BDS，把所有和当前草地
  11 有水管连接的草地找出来，标记成有水源供应。
  12 */
  13 #include <iostream>
  14 #include <queue>
  15 using namespace std;
  16 const int N=60;
  17 int step[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
  18 struct Pipe
  19 {
  20         bool up,right,down,left;
  21         Pipe(bool u=0,bool r=0,bool d=0,bool l=0)
  22         {
  23                 up=u;right=r;down=d;left=l;
  24         }
  25 };
  26 
  27 Pipe pipe[11];
  28 bool p[11][4]={{1,0,0,1},{1,1,0,0},{0,0,1,1},{0,1,1,0},
  29                            {1,0,1,0},{0,1,0,1},{1,1,0,1},{1,0,1,1},
  30                            {0,1,1,1},{1,1,1,0},{1,1,1,1}};
  31 int n,m;
  32 char map[N][N];
  33 bool graph[N][N];
  34 struct Point
  35 {
  36         int x,y;
  37         Point(int xx=0,int yy=0)
  38         {
  39                 x=xx;y=yy;
  40         }
  41 };
  42 void init()
  43 {
  44         for(int i=0;i<11;i++)
  45         {
  46                 pipe[i].up=p[i][0];
  47                 pipe[i].right=p[i][1];
  48                 pipe[i].down=p[i][2];
  49                 pipe[i].left=p[i][3];
  50         }
  51 }
  52 void BFS(int i,int j)
  53 {
  54         queue<Point> q;
  55         graph[i][j]=true;
  56         q.push(Point(i,j));
  57         int x,y;
  58         int tmp1,tmp2;
  59         while(!q.empty())
  60         {
  61                 x=q.front().x;
  62                 y=q.front().y;
  63                 q.pop();
  64                 tmp1=map[x][y]-'A';
  65                 int x1,y1;
  66                 for(int k=0;k<4;k++)
  67                 {
  68                     if(p[tmp1][k]==false)
  69                 continue;
  70             x1=x+step[k][0];
  71             y1=y+step[k][1];
  72             if(x1<0||x1>=n||y1<0||y1>=m)
  73                 continue;
  74             tmp2=map[x1][y1]-'A';
  75             if(!graph[x1][y1]&&p[tmp2][(k+2)%4]==true)
  76             {
  77                 graph[x1][y1]=true;
  78                 q.push(Point(x1,y1));
  79             }
  80 
  81                 }
  82         }
  83 }
  84 int wellsprings()
  85 {
  86         memset(graph,0,sizeof(graph));
  87         int ans=0;
  88         for(int i=0;i<n;i++)
  89                 for(int j=0;j<m;j++)
  90                 {
  91                         if(!graph[i][j])
  92                         {
  93                                 ans++;
  94                                 BFS(i,j);
  95                         }
  96                 }
  97         return ans;
  98 }
  99 int main()
 100 {
 101         init();
 102         while(1)
 103         {
 104                 cin>>n>>m;
 105                 if(n<=0&&m<<0) break;
 106                 for(int i=0;i<n;i++)
 107                         for(int j=0;j<m;j++)
 108                                 cin>>map[i][j];
 109                 cout<<wellsprings()<<endl;
 110         }
 111 }