次题的关键是把稻田的中心点抽象成图中的点，两中心点有水管相连表示两点连通，这样，此题就转化成了求图的连通分支数目
View Code
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 char grid[52][52]; 6 char map[52][52]; 7 int m,n; 8 int dir[4][2] = {{-1,0},{0,1},{0,-1},{1,0}}; // 上，右，左，下 9 //编号分别为 0，1，2，3 10 int figure[11][5] = //figure[i][0]存管子的数目 11 { 12 {2,0,2}, //A 13 {2,0,1}, //B 14 {2,3,2}, //C 15 {2,1,3}, //D 16 {2,0,3}, //E 17 {2,2,1}, //F 18 {3,0,2,1}, //G 19 {3,0,3,2}, //H 20 {3,1,2,3}, //I 21 {3,0,1,3}, // J 22 {4,0,1,2,3} //K 23 }; 24 //从（x,y）位置稻田的中心进行深度优先搜索 25 void dfs(int x,int y) 26 { 27 int t1,t2,xi,yi,i,j,temp; 28 grid[x][y] = '*'; //保证不会重复搜索 29 t1 = map[x][y] - 'A'; //判断是哪种水管 30 for(i = 1; i <= figure[t1][0]; i++) 31 { 32 temp= figure[t1][i]; 33 xi = x+dir[temp][0]; 34 yi = y+ dir[temp][1]; 35 if(xi >= m || yi >= n || xi < 0 || yi < 0) continue; //越界 36 if(grid[xi][yi] == '*') continue; //被搜到过 37 t2 = map[xi][yi] - 'A'; 38 for(j = 1; j <= figure[t2][0]; j++) //判断两中心是否连通 39 { 40 if(temp + figure[t2][j] == 3 ) 41 break; 42 } 43 if( j <= figure[t2][0]) //是break掉的，证明两中心连通 44 { 45 dfs(xi,yi); 46 } 47 } 48 } 49 50 51 //该题的想法是以稻田的水管为点，如果两稻田的水管的中心点可以连通，则两稻田可共用一水源 52 //关键是判断两稻田中心点是否是连通的，用map[i][j] 记录稻田水管的形状，用grid[i][j]表示水管中心是否 53 //被搜索过，搜索过标记*，未被搜索过标记为@ 54 int main() 55 { 56 // freopen("in.cpp","r",stdin); 57 // freopen("out.cpp","w",stdout); 58 while(true) 59 { 60 int i,j; 61 cin>>m>>n; 62 if(m<0 || n < 0) 63 break; 64 memset(grid,'@',sizeof(grid)); 65 for(i=0; i< m; i++) 66 { 67 scanf("%s",map[i]); 68 } 69 int count = 0; 70 for(i = 0; i< m; i++) 71 { 72 for( j = 0; j < n; j++) 73 { 74 if(grid[i][j] == '@') 75 { 76 dfs(i,j); 77 count++; 78 } 79 } 80 } 81 cout<<count<<endl; 82 } 83 return 0; 84 }