题目大意

有一个 $n\times m$ 的网格，每个网格可以填 $0$ 到 $2^k-1$ 范围内的数字。现在从左上角走到右下角，每次可以选择往右边或往下走一步。如果路径上所有数字异或和为 $0$，称这样的路径为好路径。给定一条路径 $s$，$\texttt{D}$ 表示往下走，$\texttt{R}$ 表示往右走。问，是否存在一个网格，使得这条路径 $s$ 是唯一的好路径。

思路

考虑用最少的数字填完整个表格，假设数字范围为 $0$ 到 $2^t-1$，只要 $t\le k$，就满足情况，否则不满足情况。

对于给定的路线 $s$，异或和为 $0$，可以将路径上所有位置全部设置为 $0$。

考虑在路线 $s$ 变化 $1$ 步的路线，也就是拐角处。为了让这些路线异或和不为 $0$，分别填 $2^0,2^1,2^3\cdots$，同时在同一条斜线上填同样的数字，其余位置填 $0$。这样保证你只要走了路线 $s$ 之外的线路，在最终的异或和上都会出现新的 $1$。

但这样不是最优的，可以发现，如果出现连续的 $2$ 个拐弯，$2$ 个拐角可以填相同的数字。

同理可以模拟出 $3$ 个连续的拐角需要 $2$ 个不同的数字，
$4$ 个连续的拐角需要 $2$ 个不同的数字，如果有 $x$ 个连续的拐角，那么 $x/2$ 个不同的数组。

时间复杂度为 $O(T(n+m))$。

AC Code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=105;
int n,m,k;
char a[N];
void solve(){
	cin>>n>>m>>k>>a+1;
	for(int i=1;i<n+m-2;i++) if(a[i]!=a[i+1]) i++,k--;
	if(k>=0) cout<<"Yes\n";
	else cout<<"No\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}