水流(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即可；
代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <climits>

#include <cstring>

#include <string>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <vector>

#include <list>

#include <ext/rope>

#define rep(i,m,n) for(i=m;i<=n;i++)

#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)

#define vi vector<int>

#define pii pair<int,int>

#define mod 1000000007

#define inf 0x3f3f3f3f

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define ll long long

#define pi acos(-1.0)

const int maxn=1e4+;

const int dis[][]= {{,},{-,},{,-},{,}};

using namespace std;

using namespace __gnu_cxx;

ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}

ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}

int n,m,cnt,vis[][];

pair<int,pii >a[maxn];

char p[][];

void dfs(int x,int y)

{

    vis[x][y]=;

    for(int i=; i<; i++)

    {

        int l=x+dis[i][],r=y+dis[i][];

        if(l>=&&l<n&&r>=&&r<m&&!vis[l][r]&&p[l][r]>=p[x][y])

            dfs(l,r);

    }

}

int main()

{

    int i,j,k,t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        cnt=;

        j=;

        memset(vis,,sizeof(vis));

        rep(i,,n-)

        scanf("%s",p[i]);

        rep(i,,n-)rep(k,,m-)

        a[j++]=mp(p[i][k],mp(i,k));

        sort(a,a+j);

        rep(i,,j-)if(!vis[a[i].se.fi][a[i].se.se])

        {

            ++cnt,dfs(a[i].se.fi,a[i].se.se);

        }

        printf("%d\n",cnt);

    }

    //system ("pause");

    return ;

}