引水入城 WA 50分

#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 1e9;
struct Zones
{
	//用于dfs的结构体
	int l , r;//此点能覆盖的 沙漠 区间
	bool vis;//访问标记
}zone[510][510];
struct Lines
{
    //用于 贪心区间覆盖 的结构体
	int l , r;
}line[510];
int ans = 0 , desert = 0 , n , m;
// ans:若能完成任务所用水泵数量
// desert:不能覆盖数目
int high[510][510];//读入的高度

bool check(int a , int b , int x , int y)
{
	//在dfs中 判断 能否进行搜索
	if(high[a][b] <= high[x][y]) return 0;
	if(x == 0 || x > n) return 0;
	if(y == 0 || y > m) return 0;
	return 1;
}

void change(int a , int b , int x , int y)
{
	//在dfs中进行 修改可覆盖区间
	zone[a][b].l = min(zone[a][b].l , zone[x][y].l);
	zone[a][b].r = max(zone[a][b].r , zone[x][y].r);
}

void dfs(int x , int y)
{
	zone[x][y].vis = 1;
	if(x == n)
		zone[x][y].l = zone[x][y].r = y;
	else 
		zone[x][y].l = INF , zone[x][y].r = 0;
	if(check(x , y , x - 1, y))
	{
		if(!zone[x - 1][y].vis)
			dfs(x - 1, y);
		change(x , y , x - 1 , y);
	}
	if(check(x , y , x + 1 , y))
	{
		if(!zone[x + 1][y].vis)
			dfs(x + 1 , y);
		change(x , y , x + 1 , y);
	}
	if(check(x , y , x , y - 1))
	{
		if(!zone[x][y - 1].vis)
			dfs(x , y - 1);
		change(x , y , x , y - 1);
	}
	if(check(x , y , x , y + 1))
	{	
		if(!zone[x][y + 1].vis)
			dfs(x , y + 1);
		change(x , y , x , y + 1);
	}
}

bool cmp(Lines a , Lines b)
{
	if(a.l != b.l)
		return a.l < b.l;
	else 
		return a.r > b.r;
}

void GetAns()
{
	//贪心覆盖
	int last = 1 , next = 0;
	for(int i = 1; i <= m; i++)
	{
		next = max(next , line[i].r);
		if(line[i + 1].l > last)
			ans++ , last = next;
		if(last >= m) return;
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <=m; j++)
		{
			cin >> high[i][j];
		}
	}
	for(int i = 1; i <= m; i++)
	{
		dfs(1 , i);
		line[i].l = zone[1][i].l;
		line[i].r = zone[1][i].r;
	}
	for(int i = 1; i <= m; i++)
	{
		if(!zone[n][i].l)
			desert++;
	}
	if(desert)
	{
		cout << 0 << endl << desert << endl;
		return 0;
	}
	sort(line + 1 , line + m + 1 , cmp);
	line[m + 1].l = INF;
	GetAns();
	cout << 1 << endl << ans << endl; 
	return 0;
}