描述
在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N行M列的矩形，其中每个格子都代表一座城市，每座城市都有一个海拔高度。
为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此，只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。
由于第N行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。
格式
输入格式
输入文件的每行中两个数之间用一个空格隔开。
输入的第一行是两个正整数N和M，表示矩形的规模。
接下来N行，每行M个正整数，依次代表每座城市的海拔高度。
输出格式
输出有两行。如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少建造几个蓄水厂；如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有几座干旱区中的城市不可能建有水利设施。
限制
每个测试点1s
提示
本题共有10个测试数据，每个数据的范围如下表所示：
测试数据编号 能否满足要求 N M
1 不能 ≤ 10 ≤ 10
2 不能 ≤ 100 ≤ 100
3 不能 ≤ 500 ≤ 500
4 能 = 1 ≤ 10
5 能 ≤ 10 ≤ 10
6 能 ≤ 100 ≤ 20
7 能 ≤ 100 ≤ 50
8 能 ≤ 100 ≤ 100
9 能 ≤ 200 ≤ 200
10 能 ≤ 500 ≤ 500
对于所有的10个数据，每座城市的海拔高度都不超过10^6。
来源
noip2010提高组复赛
解析：1.从上往下进行染色，然后统计第 n 行未被染色的数量 s ，若s>0，则输出 0 s；
为什么选择从上往下染色，而不是下方的从下往上染色，还能生一次搜索呢。（我买个关子，自己做的时候就知道了。）
2.从下往上进行两次染色，第一次，从左往右进行染色，得到每一个第一行的点所能覆盖的左界；
第二次，从右往左进行染色，得到每一个第一行的点所能覆盖的右界。
3.贪心。假设当前覆盖区间为[l，r]，枚举第一行的点，从中选取能与当前区间[l，r]连接起来，并且向右延伸最远的点，作为下一个蓄水场建立点。
代码：
#include<cstdio>
#include<algorithm>
#define maxn 500
using namespace std;
int n,m,h[maxn+20][maxn+20];
int color[maxn+20][maxn+20];
struct node{int x,y;}q[maxn*maxn+20];
struct tnode{int left,right;}p[maxn+20];
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
bool cmp(tnode a,tnode b)
{
if(a.left<b.left)return 1;
if(a.left>b.left)return 0;
return a.right>b.right;
}
void bfs_1(int a,int b)
{
int i,j,k,l=0,r=0;
q[0].x=a,q[0].y=b;
while(l<=r)
{
for(k=0;k<4;k++)
{
i=q[l].x+dx[k],j=q[l].y+dy[k];
if(i>=1 && i<=n && j>=1 && j<=m &&
color[i][j]!=-1 && h[i][j]<h[q[l].x][q[l].y])
q[++r].x=i,q[r].y=j,color[i][j]=-1;
}
l++;
}
}
void bfs_2(int a,int b,int c)
{
int i,j,k,l=0,r=0;
q[0].x=a,q[0].y=b;
while(l<=r)
{
for(k=0;k<4;k++)
{
i=q[l].x+dx[k],j=q[l].y+dy[k];
if(i>=1 && i<=n && j>=1 && j<=m &&
color[i][j]<c && h[i][j]>h[q[l].x][q[l].y])
q[++r].x=i,q[r].y=j,color[i][j]=color[a][b];
}
l++;
}
}
int main()
{
int i,j,k,s,l,r;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&h[i][j]);
for(i=1;i<=m;i++)color[1][i]=-1;
for(i=1;i<=m;i++)bfs_1(1,i);
for(s=0,i=1;i<=m;i++)if(color[n][i]!=-1)s++;
if(s>0)
{
printf("%d\n%d\n",0,s);
return 0;
}
for(i=1;i<=m;i++)p[i].left=p[i].right=0;
for(i=1;i<=m;i++)
if(color[n][i]<1)color[n][i]=i,bfs_2(n,i,1);
for(i=1;i<=m;i++)
if(color[1][i]>=1 && color[1][i]<=m)p[i].left=color[1][i];
for(i=m;i>=1;i--)
if(color[n][i]<m+1)color[n][i]=m+i,bfs_2(n,i,m+1);
for(i=1;i<=m;i++)
if(color[1][i]>=m+1 && color[1][i]<=m+m)p[i].right=color[1][i]-m;
s=0,r=0;
while(r<m)
{
for(k=0,i=1;i<=m;i++)
if(p[i].left==r+1)k=max(k,p[i].right);
r=k,s++;
for(i=1;i<=m;i++)
if(p[i].right>r && p[i].left<=r)p[i].left=r+1;
}
printf("%d\n%d\n",1,s);
return 0;
}