Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

全球气候变暖，小镇A面临水灾。于是你必须买一些泵把水抽走。泵的抽水能力可以认为是无穷大，但你必须把泵放在合适的位置

，从而能使所有的水能流到泵里。小镇可以认为是N * M的矩阵。矩阵里的每个单元格都是一个‘a’- ‘z’小写字母，该小写

字母表示该格子的高度，字母大的表示该单元格比较高，反之，表示该格子高度比较低。当前单元格的水可以流到上、下、左、

右四个格子，但必须满足这些格子的高度是小于或者等于当前格子的高度。现在，给你一些N * M的矩阵，你至少要买多少个泵

，才能把所有格子的水都能被抽走？

【输入格式】

多组测试数据。

第一行：K，表示有K组测试数据。 1 <= K <= 5.

接下来有K组测试数据，每组测试数据格式如下：

第一行：两个正数, N , M . 1 <= N, M <= 50，表示小镇的大小。

接下来有N行，每行有M个小写字母，表示小镇的地图。

【输出格式】

共K行，每行对应一组数据。至少要买多少个泵，才能把所有格子的水都能抽走。

Sample Input

2

5 5

ccccc

cbbbc

cbabc

cbbbc

ccccc

4 9

cbabcbabc

cbabcbabc

cbabcbabc

cbabcbabc

Sample Output

1

2

Sample Input2

1

11 11

ccccccccccc

caaaaaaaaac

caaaaaaaaac

caazpppzaac

caapdddpaac

caapdddpaac

caapdddpaac

caazpppzaac

caaaaaaaaac

caaaaaaaaac

ccccccccccc

Sample Output2

2

【题目链接】:

【题解】

从最低点开始bfs,看它能到哪些位置;(水泵的位置放在最低点显然更优);

每次都从没有被覆盖过的部分里面找一个最低点进行bfs;

因为高度从’a’->’z’，所以枚举起点的高度为’a’->’z’即可;

遇到一个符合要求的起点就递增答案；

【完整代码】

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int MAXN = 55;const int dx[5] = {
    0,1,-1,0,0};const int dy[5] = {
    0,0,0,1,-1};int n,m;int dt[MAXN][MAXN];bool bo[MAXN][MAXN];queue 
         
          
            > dl;int main(){ //freopen("D:\\rush.txt","r",stdin); int T; cin >> T; while (T--) { memset(bo,false,sizeof(bo)); cin >> n >> m; for (int i = 1;i <= n;i++) { string s; cin >> s; for (int j = 0;j <=m-1;j++) { dt[i][j+1] = s[j]-'a'; bo[i][j+1] = true; } } int ans = 0; for (int mi = 0;mi <= 25;mi++) for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) if (dt[i][j] == mi&& bo[i][j]) { ans++; bo[i][j] = false; dl.push(make_pair(i,j)); while (!dl.empty()) { int x = dl.front().first,y = dl.front().second; dl.pop(); for (int p=1;p <= 4;p++) { int tx = x+dx[p],ty =y+dy[p]; if (bo[tx][ty]&&dt[tx][ty]>=dt[x][y]) { bo[tx][ty] = false; dl.push(make_pair(tx,ty)); } } } } cout << ans << endl; } return 0;}