水流(water)
题目描述
全球气候变暖,小镇A面临水灾,于是你必须买一些泵把水抽走。泵的抽水能力可以认为是无穷大,但你必须把泵放在合适的位置,从而能使所有的水能流到泵里。 小镇可以认为是N×M的矩阵,矩阵里的每个单元格都是一个a~z小写字母,该小写字母表示该格子的高度,字母大的表示该单元格比较高,反之表示该格子高度 比较低。当前单元格的水可以流到上、下、左、右四个格子,但必须满足这些格子的高度是小于或者等于当前格子的高度。现在,给你一些NXM的矩阵,你至少要 买多少个泵,才能把所有格子的水都抽走?
输入
多组测试数据。
第1行:K,表示有K组测试数据,1≤K≤5。
接下来有K组测试数据,每组测试数据格式如下:
第1行:两个正整数,N,M。1≤N,M≤50,表示小镇的大小。
接下来有N行,每行有M个小写字母,表示小镇的地图。
输出
共K行,每行对应一组数据。至少要买多少个泵,才能把所有格子的水都抽走。
样例输入
2
5 5
ccccc
cbbbc
cbabc
cbbbc
ccccc
4 9
cbabcbabc
cbabcbabc
cbabcbabc
cbabcbabc
样例输出
1
2
解析:比较简单的dfs, 刚开始想从‘z’ 搜到 ‘a’, 样例都没过, 后来用‘a’搜到‘z’, 果然过了。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<vector> #include <climits> #include <map> using namespace std; const int MAXN = 53; int N, M; char maze[MAXN][MAXN]; char s[MAXN][MAXN]; int xi[] = {0, 0, -1, 1}; int yi[] = {1, -1, 0, 0}; void dfs(int x, int y) { s[x][y] = 1; for(int i = 0; i < 4; i++) { int nx = x + xi[i]; int ny = y + yi[i]; //printf("%d %d %c ", nx, ny,maze[nx][ny]); if(nx>=0 && nx < N && ny >= 0 && ny < M && s[nx][ny] == 0 && maze[nx][ny] >= maze[x][y]) { dfs(nx, ny); } } } int main() { int t = 0; scanf("%d", &t); while(t--) { scanf("%d%d", &N, &M); for(int i = 0; i < N; i++) { scanf("%s", maze[i]); } memset(s, 0, sizeof(s)); int cnt = 0; for(char c = 'a'; c <= 'z'; c++) { for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { if(s[i][j] == 0 && maze[i][j] == c){ dfs(i, j); cnt++; } } } } printf("%d ", cnt); } return 0; }