題意:給如一個地圖,每一個方塊上都有一條河流,如果兩個方塊間的河流連接配接在一起,那他們就是同一條河流。每條河流必須有一個源點。這樣才能保證每條河流所在的方塊上的農田能被灌溉到。
簡化一下提議,就是求有多少條河流。
思路:從給出的11塊方塊種類,可以計算兩塊農田一上下或者左右連在一起是否能構成一條河流,如果能,就用并查集連在一起,最後計算有多少個節點就OK了。
思路簡單,代碼不做注釋!
#include<iostream>
using namespace std;
#define MAXN 505
struct Farm {
bool up;
bool down;
bool left;
bool right;
}farms[MAXN];
int father[MAXN * MAXN];
int findSet(int a) {
if (a == father[a]) {
return a;
} else {
return findSet(father[a]);
}
}
void Union(int a,int b) {
int x = findSet(a);
int y = findSet(b);
if (x == y) {
return;
}
father[y] = x;
return;
}
int findRoot(int n) {
int count = 0;
for (int i=0; i<n; i++) {
if (father[i] == i) {
count ++;
}
}
return count;
}
void init() {
for (int i=0; i<MAXN*MAXN; i++) {
father[i] = i;
}
farms[0].up = 1;
farms[0].left = 1;
farms[1].up = 1;
farms[1].right = 1;
farms[2].left = 1;
farms[2].down = 1;
farms[3].right = 1;
farms[3].down = 1;
farms[4].up = 1;
farms[4].down = 1;
farms[5].left = 1;
farms[5].right = 1;
farms[6].left = 1;
farms[6].up = 1;
farms[6].right = 1;
farms[7].left = 1;
farms[7].up = 1;
farms[7].down = 1;
farms[8].left = 1;
farms[8].down = 1;
farms[8].right = 1;
farms[9].up = 1;
farms[9].right = 1;
farms[9].down = 1;
farms[10].left = 1;
farms[10].right = 1;
farms[10].up = 1;
farms[10].down = 1;
}
char map[MAXN][MAXN];
int main() {
int n, m;
while (cin>>n>>m) {
if (n == -1 && m == -1) {
break;
}
init();
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cin>>map[i][j];
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if ((i - 1) >= 0) {
if (farms[map[i-1][j]-'A'].down && farms[map[i][j]-'A'].up) {
int x = i * m + j;
int y = (i - 1) * m + j;
Union(x, y);
}
}
if ((i + 1) < n) {
if (farms[map[i+1][j]-'A'].up && farms[map[i][j]-'A'].down) {
int x = i * m + j;
int y = (i + 1) * m + j;
Union(x, y);
}
}
if ((j - 1) >= 0) {
if (farms[map[i][j-1]-'A'].right && farms[map[i][j]-'A'].left) {
int x = i * m + j;
int y = i * m + (j - 1);
Union(x, y);
}
}
if ((j + 1) < m) {
if (farms[map[i][j+1]-'A'].left && farms[map[i][j]-'A'].right) {
int x = i * m + j;
int y = i * m + (j + 1);
Union(x, y);
}
}
}
}
cout<<findRoot(n * m)<<endl;
}
}