题目大意：有11种水管放置的方式，给一个m*n的大农田，每块小农田有各自的水管放置方式，问至少需要多少个水源才能让所有小农田都有水流过其中的水管。
解题思路：dfs将11种方式的上下左右可通表示出来，如果其某个方向的放置放置可以与其对接就进入下一层并标记。并查集方式类似，将11种方式的上下左右可通表示出来，如果其某个方向的放置放置可以与其对接就合并，最后判断有几个集合。
dfs方法ac代码：
#include <iostream>
#include <cstring>
using namespace std;
int map[15][4]={
1,0,1,0,1,0,0,1,0,1,1,0,
0,1,0,1,1,1,0,0,0,0,1,1,1,0,1,1,1,1,1,0,
0,1,1,1,1,1,0,1,1,1,1,1}, n, vis[55][55], m;
int dx[4]={
-1,1,0,0}, dy[4]={
0,0,-1,1}, sum, down[4]={
1,0,3,2};
char a[55][55];
bool judge(int x, int y, int i)
{int temp, t1, t2;t1 = a[x][y] - 'A';if (map[t1][i] && x+dx[i] >= 0 && x+dx[i] < m && y+dy[i] >= 0 && y+dy[i] < n);elsereturn 0;temp = down[i];t2 = a[x+dx[i]][y+dy[i]] - 'A';if (map[t1][i] && !vis[x+dx[i]][y+dy[i]] && map[t2][temp])return 1;
return 0;
}
void dfs(int x, int y)
{vis[x][y] = 1;for (int i=0; i<4; i++)if (judge(x, y, i)){dfs(x+dx[i], y+dy[i]); }}
int main()
{while (scanf("%d%d", &m, &n)!=EOF){memset(vis, 0, sizeof(vis));sum = 0;if (n == -1 && m == -1)break;for (int i=0; i<m; i++)scanf("%s", a[i]);for (int i=0; i<m; i++)for (int j=0; j<n; j++)if (!vis[i][j]){dfs(i, j);sum++; }printf("%d\n", sum);}
return 0;
}
并查集方法ac代码：
#include <iostream>
#include <cstring>
#include <set>
using namespace std;
set <int>se;
int map[15][4]={
1,0,1,0,1,0,0,1,0,1,1,0,
0,1,0,1,1,1,0,0,0,0,1,1,1,0,1,1,1,1,1,0,
0,1,1,1,1,1,0,1,1,1,1,1}, n, m;
int dx[4]={
-1,1,0,0}, dy[4]={
0,0,-1,1}, pre[255];
int t1, t2, temp, down[4]={
1,0,3,2};
char a[55][55];
int find(int x)
{if (x != pre[x])pre[x] = find(pre[x]);
return pre[x];
}
void Union(int x, int y)
{int fx=find(x), fy=find(y);if (fx != fy)pre[fx] = fy;
}
int main()
{while (scanf("%d%d", &m, &n)!=EOF){if (n == -1 && m == -1)break;for (int i=1; i<=n*m; i++)pre[i] = i;for (int i=0; i<m; i++)scanf("%s", a[i]);for (int i=0; i<m; i++)for (int j=0; j<n; j++){t1 = a[i][j] - 'A';for (int k=0; k<4; k++)if (map[t1][k] && i+dx[k] >= 0 && i+dx[k] < m&& j+dy[k] >= 0 && j+dy[k] < n){t2 = a[i+dx[k]][j+dy[k]] - 'A'; temp = down[k];if (map[t2][temp])Union(i*n+j+1, (i+dx[k])*n+(j+dy[k])+1); }}for (int i=1; i<=n*m; i++)se.insert(find(i)); printf("%d\n", se.size());se.clear();}
return 0;
}