P1514 引水入库

1. 70分
2. 样例：
3. 6 7 WA
4. 5 TLE

• 代码：

#include <bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
}al[1000001];
struct cv{
	int be,ed;
}mof[1000001];
int n,m,high_max=INT_MIN,high_min=INT_MAX;
int mod[505][505],book[505][505],bok[505];
int head,tail,fey,fef,mode[505];
int ne[4][2]={0,1,-1,0,0,-1,1,0};
void bfs(int x,int y)
{
	al[tail].x=x;
	al[tail].y=y;
	book[x][y]=1;
	tail++;
	while(head<tail)
	{
		for(int i=0;i<=3;i++)
		{
			int tx=al[head].x+ne[i][0];
			int ty=al[head].y+ne[i][1];
			if(tx<1||tx>n||ty<1||ty>m)
				continue;
			if(mod[tx][ty]<mod[al[head].x][al[head].y] && book[tx][ty]==0)
			{
				if(tx==n)
				{
					fey++;
					bok[ty]=1;
					mode[fey]=ty;
				}
				book[tx][ty]=1;
				al[tail].x=tx;
				al[tail].y=ty;
				tail++;
			}
		}
		head++;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>mod[i][j];
	for(int i=1;i<=m;i++)
	{
		fey=0;
		head=0,tail=0;
		memset(mode,0,sizeof(mode));
		memset(book,0,sizeof(book));
		bfs(1,i);
		sort(mode+1,mode+1+fey);
		fef++;
		mof[fef].be=mode[1];
		mof[fef].ed=mode[fey];
	}
	int cnt=0;
	for(int i=1;i<=m;i++)
		if(bok[i]==0)
			cnt++;
	if(cnt>0)
	{
		cout<<0<<endl;
		cout<<cnt;
		return 0;
	}
	cnt=1;
	int st=mof[1].ed,r=0;
	for(int i=2;i<=fef && st<fef;i++)
	{
		while(st+1 >= mof[i].be && i<=fef)
			r=max(r,mof[i].ed),i++;
		i--;
		cnt++;
		st=max(st,r);
	}
	cout<<1<<endl;
	cout<<cnt;
	return 0;
}