洛谷1514 引水入城

原题链接

对于第一个问题，显然(DFS)或(BFS)一遍看看最后一排是不是全部被搜到即可。
对于第二个问题，考虑贪心，求出第一排每个格子最大能够覆盖多少最后一排的格子，即求左端右端（显然覆盖的格子都是连续的，若不为连续，则那个断开的格子定无法到达）。
可以使用(DP)来求出，设(L[x][y],R[x][y])分别表示对于格子((x,y))，从它出发能够覆盖最后一排的格子的最左端和最右端，显然(L[x][y] = min { L[x ^ prime][y ^ prime] },R[x][y] = max { R[x ^ prime][y ^ prime] })，((x ^ prime, y ^ prime))是格子((x, y))能够到达的格子。
这里我是使用记忆化搜索来求的，这样可以在用(DFS)求解第一个问题的时候同时求出。
因为据说这题若构造特殊数据能把(DFS)弄爆栈，所以我使用了手工栈，另外附上非手工栈版本。

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 510;
struct dd{
	int i, x, y, xx, yy;
};
dd sta[N * N];
int a[N][N], L[N][N], R[N][N], mo_x[4] = {0, 0, 1, -1}, mo_y[4] = {1, -1, 0, 0}, n, m, tp;
bool v[N][N];
inline int re()
{
	int x = 0;
	char c = getchar();
	bool p = 0;
	for (; c < '0' || c > '9'; c = getchar())
		p |= c == '-';
	for (; c >= '0' && c <= '9'; c = getchar())
		x = x * 10 + c - '0';
	return p ? -x : x;
}
inline int minn(int x, int y)
{
	return x < y ? x : y;
}
inline int maxn(int x, int y)
{
	return x > y ? x : y;
}
/*非手工栈版本
void dfs(int x, int y)
{
	v[x][y] = 1;
	int i, xx, yy;
	for (i = 0; i < 4; i++)
	{
		xx = x + mo_x[i];
		yy = y + mo_y[i];
		if (a[xx][yy] < a[x][y] && xx > 0 && xx <= n && yy > 0 && yy <= m)
		{
			if (!v[xx][yy])
				dfs(xx, yy);
			L[x][y] = minn(L[x][y], L[xx][yy]);
			R[x][y] = maxn(R[x][y], R[xx][yy]);
		}
	}
}
*/
void dfs(int xo, int yo)
{
	sta[tp = 1].x = xo;
	sta[1].y = yo;
start:
	v[sta[tp].x][sta[tp].y] = 1;
	for (sta[tp].i = 0; sta[tp].i < 4; sta[tp].i++)
	{
		sta[tp].xx = sta[tp].x + mo_x[sta[tp].i];
		sta[tp].yy = sta[tp].y + mo_y[sta[tp].i];
		if (a[sta[tp].xx][sta[tp].yy] < a[sta[tp].x][sta[tp].y] && sta[tp].xx > 0 && sta[tp].xx <= n && sta[tp].yy > 0 && sta[tp].yy <= m)
		{
			if (!v[sta[tp].xx][sta[tp].yy])
			{
				sta[tp + 1].x = sta[tp].xx;
				sta[tp + 1].y = sta[tp].yy;
				tp++;
				goto start;
			}
		end:
			L[sta[tp].x][sta[tp].y] = minn(L[sta[tp].x][sta[tp].y], L[sta[tp].xx][sta[tp].yy]);
			R[sta[tp].x][sta[tp].y] = maxn(R[sta[tp].x][sta[tp].y], R[sta[tp].xx][sta[tp].yy]);
		}
	}
	if (--tp)
		goto end;
}
int main()
{
	int i, j, s = 0, l = 1, r;
	bool p = 0;
	n = re();
	m = re();
	memset(L, 60, sizeof(L));
	for (i = 1; i <= m; i++)
		L[n][i] = R[n][i] = i;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++)
			a[i][j] = re();
	for (i = 1; i <= m; i++)
		if (!v[1][i])
			dfs(1, i);
	for (i = 1; i <= m; i++)
		if (!v[n][i])
		{
			p = 1;
			s++;
		}
	if (p)
	{
		printf("0
%d", s);
		return 0;
	}
	for (s = r = 0; l <= m; r = 0, s++)
	{
		for (i = 1; i <= m; i++)
			if (L[1][i] <= l)
				r = maxn(r, R[1][i]);
		l = r + 1;
	}
	printf("1
%d", s);
	return 0;
}