题解：CF1766C Hamiltonian Wall

zhangmuning1016 · 2025-03-31 15:04:10 · 题解

题意

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

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

很明显，这是一道关于动态规划的题目。为什么没有人用动态规划呢？
状态转移方程：
如果在第 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。

代码


#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

题意

思路

代码