时限：1000ms 内存限制：10000K总时限：3000ms 描述：
一农场由图所示的十一种小方块组成，蓝色线条为灌溉渠。若相邻两块的灌溉渠相连则只需一口水井灌溉。
输入：
给出若干由字母表示的最大不超过50×50具体由(m，n)表示，的农场图
输出：
编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。
输入样例：
2 2 DK HF 3 3 ADC FJK IHE -1 -1
输出样例：
【ACM|农场灌溉问题】2 3
#include #includeusing namespace std;
int m, n;
bool InterLinked(string field[], int same, int diff1, int diff2, int dir) { if (dir == 0)//left-right { if (field[same][diff1] == 'A' || field[same][diff1] == 'C' || field[same][diff1] == 'E' || field[same][diff1] == 'H' || field[same][diff2] == 'B' || field[same][diff2] == 'D' || field[same][diff2] == 'E' || field[same][diff2] == 'J') return false;
else return true;
} else//up-down { if (field[diff1][same] == 'A' || field[diff1][same] == 'B' || field[diff1][same] == 'F' || field[diff1][same] == 'G' || field[diff2][same] == 'C' || field[diff2][same] == 'D' || field[diff2][same] == 'F' || field[diff2][same] =='I') return false;
else return true;
} } void DigWells(string field[], int row, int col, bool haveWell[]) { if (col - 1 >= 0 && !haveWell[row * n + col - 1] && InterLinked(field, row, col - 1, col, 0)) { haveWell[row * n + col - 1] = true;
DigWells(field, row, col - 1, haveWell);
} if (col + 1 < n && !haveWell[row * n + col + 1] && InterLinked(field, row, col, col + 1, 0)) { haveWell[row * n + col + 1] = true;
DigWells(field, row, col + 1, haveWell);
} if (row - 1 >= 0 && !haveWell[(row - 1) * n + col] && InterLinked(field, col, row - 1, row, 1)) { haveWell[(row - 1) * n + col] = true;
DigWells(field, row - 1, col, haveWell);
} if (row + 1 < m && !haveWell[(row + 1) * n + col] && InterLinked(field, col, row, row + 1, 1)) { haveWell[(row + 1) * n + col] = true;
DigWells(field, row + 1, col, haveWell);
} } int main(int argc, char *argv[]) { cin >> m >> n;
while (m != -1 && n != -1) { string *field = new string[m];
bool *haveWell = new bool[m * n];
int count = 0;
memset(haveWell, 0x00, sizeof(bool) * m * n);
for (int i = 0;
i < m;
i++) cin >> field[i];
for (i = 0;
i < m;
i++) { for (int j = 0;
j < n;
j++) { if (!haveWell[i * n + j]) { count++;
haveWell[i * n + j] = true;
DigWells(field, i, j, haveWell);
} } } cout << count << endl;
delete []field;
delete []haveWell;
cin >> m >> n;
} return 0;
}
推荐阅读
