hdu 1198农田灌溉

通过这道题，我只想要说图论的题，建好了图，题就解了一大半了。。。

这道题建好图后，dfs暴搜就行了。。。

View Code

 1 #include<iostream>
 2 #include<cstring>
 3 const int N=60;
 4 using namespace std;
 5 
 6 int n,m;
 7 char map[N][N];
 8 int visited[N][N];
 9 int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//up/right/down/left
10 int pip[11][4]={{1,0,0,1},{1,1,0,0},{0,0,1,1},{0,1,1,0},{1,0,1,0},{0,1,0,1},{1,1,0,1},{1,0,1,1},{0,1,1,1},{1,1,1,0},{1,1,1,1}};//up/right/down/left
11 
12 void dfs(int x,int y){
13     visited[x][y]=1;
14     for(int i=0;i<4;i++){
15         int xx=x+dir[i][0];
16         int yy=y+dir[i][1];               
17         //原来的方向上要有管道，要走的点也要有对应的管道衔接。。。
18         if(!visited[xx][yy]&&xx>=0&&xx<m&&yy>=0&&yy<n&&pip[map[x][y]-'A'][i]&&pip[map[xx][yy]-'A'][(i+2)%4])
19             dfs(xx,yy);
20     }
21 }
22 
23 
24 int main(){
25     while(scanf("%d%d",&m,&n)!=EOF){
26         if(m<0||n<0)break;
27         int count=0;
28         memset(visited,0,sizeof(visited));
29         for(int i=0;i<m;i++){
30             scanf("%s",map[i]);
31         }
32         for(int i=0;i<m;i++){
33             for(int j=0;j<n;j++){
34                 if(!visited[i][j]){
35                     dfs(i,j);
36                     count++;
37                 }
38             }
39         }
40         printf("%d\n",count);
41     }
42     return 0;
43 }