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

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t048

【题解】



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

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

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

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



【完整代码】

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

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 <pair<int,int> > 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;

}