题解：CF1766C Hamiltonian Wall

题意

请你在一个矩阵中找到一条路，使这条路满足下面的条件：

路途相邻的格子必须相连。
矩阵里所有的 $\texttt{B}$ 格子都要在路径中出现。
不能经过任何 $\texttt{W}$ 格子。如果有这样的路，就输出 YES；要是找不到，就输出 NO。

思路

很明显，这是一道关于动态规划的题目。为什么没有人用动态规划呢？

dp_{i,j,k}

表示第

i

行第

j

列，经过了

k

个黑格子，是否可行。
状态转移方程：

如果在第 $0$ 行，把 $dp_{i+1,j,k+1}$ 设为 $1$ 。
如果在第 $1$ 行，把 $dp_{i-1,j,k+1}$ 设为 $1$ 。
如果下一列的格子是黑色的，并且还没到过，把 $dp_{i,j+1,k+1}$ 设为 $1$ 。
如果 $dp_{i,j,k}$ 等于 $1$ 时，表示当前状态可行，那么继续向相邻的黑格子走。循环结束后判断是否存在某一行的 $dp$ 数组的值等于总的 B 的数量。如果有，则输出 YES，没有输出 NO。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
bool fun(const vector<string>& a) {
	int m = a[0].size();
	int bsum = 0;//记录黑格子的数量。 
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == 'B') {//找到一个黑色格子 
				bsum++;
			}
		}
	}
	vector<vector<vector<bool> > > dp(2, vector<vector<bool> >(m, vector<bool>(bsum + 1, 0)));//两个大于号中要打空格，我就是因为这个原因调了好久。 

	int startX = -1, startY = -1;
	for (int i = 0; i < 2; i++) {//找到第一个黑格子为起点。 
		for (int j = 0; j < m; j++) {
			if (a[i][j] == 'B') {
				startX = i;
				startY = j;
				dp[startX][startY][1] = true;
				break;
			}
		}
		if (startX != -1) {
			break;
		}
	}
	for (int k = 1; k < bsum; k++) {
		for (int j = 0; j < m; j++) {
			for (int i = 0; i < 2; i++) {
				if (dp[i][j][k]) {//此处可行
					if (j < m - 1 && a[i][j + 1] == 'B' &&!dp[i][j + 1][k + 1]) {//向右移动
						dp[i][j + 1][k + 1] = 1;
					}
					if (i == 1 && j < m - 1 && a[0][j] == 'B' &&!dp[0][j][k + 1]) {//向上移动
						dp[0][j][k + 1] = 1;
					}
					if (i == 0 && j < m - 1 && a[1][j] == 'B' &&!dp[1][j][k + 1]) {//向下移动
						dp[1][j][k + 1] = 1;
					}
				}
			}
		}
	}

	for (int i = 0; i < 2; i++) {//检查是否有这样的路 
		for (int j = 0; j < m; j++) {
			if (dp[i][j][bsum]) {
				return true;
			}
		}
	}
	return false;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		int m;
		cin >> m;
		vector<string> a(2);
		cin >> a[0] >> a[1];
		if (fun(a)) {
			cout << "YES" << endl;
		} else {
			cout << "NO" << endl;
		}
	}
	return 0;
}

题解：CF1766C Hamiltonian Wall

文章操作

题意

思路

代码

相关推荐

评论

题解：CF1766C Hamiltonian Wall