「模拟赛20191019」A 简单DP

题目描述

给一个(n imes m)的网格，每个格子上有一个小写字母。

对于所有从左上角((1,1))到右下角((n,m))只向下或向右走的路径构成的集合，判断是否存在两条走法不同的路径，使得把它们经过的格子上的字母按顺序记下来得到的序列完全相同。

输入

第一行一个整数(T)表示数据组数，对于每组数据：
第一行两个整数(n,m)；
接下来(n)行，每行一个长度为(m)的字符串表示网格的每一行。

输出

对于每组数据，输出一行(Yes)或(No)表示是否存在这样的两条路径。

样例

样例输入

2
2 2
ab
bc
2 2
ab
cd

样例输出

Yes
No

数据范围

对于(100\%)的数据，(1leq n,m leq 1000)，(1leq Tleq 10)。

水题，考虑(DP)，假设目前考虑到第(i)行，第(j)列，要是存在这两条路径，那么它们要么都从上方走来，要么都从左边走来，或者一条从上方走来，一条从左边走来。

讨论一下，第一种情况，只要(i-1)行，(j)列可以满足就行了；第二种情况，只要(i)行，(j-1)列满足就行了；第三种情况，首先要满足(A_{i-1,j}=A_{i,j-1})，然后发现只要能走到((i-1,j-1))这个点，就一定存在这样的路径（先沿着同一条路走到((i-1,j-1))，然后分别经过((i-1,j))和((i,j-1))到达((i,j))）。

于是定义(f_{i,j})表示前(i)行，(j)列是否满足，则(f_{i,j}=f_{i-1,j}|f_{i,j-1}|(A_{i-1,j}=A_{i,j-1}))。这道题就做完了……

(Code:)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1005
char S[N][N];
int n, m, t, f[N][N];
int main()
{
	scanf("%d", &t);
	for (; t--; )
	{
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++)
			scanf("%s", S[i] + 1);
		memset(f, 0, sizeof(f));
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				f[i][j] |= f[i - 1][j] | f[i][j - 1];
				if (i > 1 && j > 1)
					f[i][j] |= (S[i][j - 1] == S[i - 1][j]);
			}
		if (f[n][m])
			puts("Yes");
		else
			puts("No");
	}
}