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

【题解】



对于第一问:从最上面那m个格子开始进行广搜就可以了；

然后看一下最下面那一行有没有被全部覆盖;

对于第二问:

要先明确；从最上面的那m个格子中的任意一个点开始，在最下面的沙漠中行成的覆盖段一定是连续的一段；(有解的前提下);

证明:

假设最上面的格子x开始进行广搜在最下面形成了两段不连续的区间

a..b c..d (b小于c)

则必然在最上面的m个点中有一个点或多个点，能覆盖b..c这个区间;



但是如果那样覆盖的话，如上图所示，那个点(或多个点)在往下覆盖的时候肯定会和x往下覆盖的路径发生重叠，而既然那个点能往下走，为什么x号节点不能往下走?这就出现矛盾了；所以x格子不可能在最下面形成不连续的两段区间(或多段),则它只能形成一段连续的区间.

则我们在判断完有解之后；

再一个一个地以最上面那个湖泊的点为起点进行广搜，到最下面；看它能覆盖的区间是什么->求出m个区间;

然后用这m个区间进行动规以求覆盖1..m所需要的最少区间数->区间数对应蓄水厂数目;

f[i] = min(f[l[k]-1]+1,f[i]);其中r[k]>=i;



【完整代码】

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <set>

#include <map>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <stack>

#include <string>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

void rel(LL &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t) && t!='-') t = getchar();

    LL sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

void rei(int &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t)&&t!='-') t = getchar();

    int sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

const int MAXN = 500+10;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

int n,m;

int a[MAXN][MAXN];

int flag[MAXN][MAXN];

bool bo[MAXN][MAXN];

int tag = 0;

queue <pii> dl;

void bfs()

{

    while (!dl.empty())

    {

        int x = dl.front().fi,y = dl.front().se;

        dl.pop();

        rep1(k,1,4)

        {

            int tx = x+dx[k],ty = y+dy[k];

            if (bo[tx][ty])

            {

                if (a[tx][ty]<a[x][y] && flag[tx][ty]!=tag)

                {

                    flag[tx][ty] = tag;

                    dl.push(mp(tx,ty));

                }

            }

        }

    }

}

int main()

{

   // freopen("F:\\rush.txt","r",stdin);

    memset(bo,false,sizeof(bo));

    rei(n);rei(m);

    rep1(i,1,n)

        rep1(j,1,m)

            rei(a[i][j]),bo[i][j] = true;

    memset(flag,0,sizeof(flag));

    tag++;

    rep1(i,1,m)

        {

            flag[1][i] = tag;

            dl.push(mp(1,i));

        }

    bfs();

    int cnt = 0;

    rep1(i,1,m)

        if (flag[n][i]==0)

            cnt++;

    if (cnt)

    {

        puts("0");

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

        return 0;

    }

    else

    {

        vector <pii> a;

        rep1(i,1,m)

        {

            tag++;

            flag[1][i] = tag;

            dl.push(mp(1,i));

            bfs();

            pii temp;

            rep1(j,1,m)

                if (flag[n][j]==tag)

                {

                    temp.fi=j;

                    break;

                }

            rep2(j,m,1)

                if (flag[n][j]==tag)

                {

                    temp.se = j;

                    break;

                }

            a.pb(temp);

        }

        int f[MAXN],len = a.size();

        memset(f,0x3f3f3f3f,sizeof f);

        f[0] = 0;

        rep1(i,1,m)

            rep1(j,0,len-1)

                if (a[j].se>=i)

                    f[i] = min(f[i],f[a[j].fi-1]+1);

        puts("1");

        printf("%d\n",f[m]);

    }

    return 0;

}