Maze Tac Toe (USACO Silver 2021 Open)

一个比较麻烦的搜索题目，代码量比较大。

状态可以定义为井字棋状态（ $3^9$ ） + 当前B的位置（ $25 \cdot 25$ ，所有非空格点），最大 $12M$ 个状态。

我们在状态空间（不是地图的位置空间）做完全搜索就可以了。状态如下定义（每个字母或数字代表一个二进制位）：

RRRRR CCCCC 22 21 20 12 11 10 02 01 00   -> 一共28个二进制位，可以放进一个整数

R和C是地图位置，00-22是棋盘上对应位置的状态（0: 空，1: O, 2: M）

官方题解算法一样，代码更短一些，区别主要是状态的编码方法不一样（没有装到一个整数里面），可以对比参考。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int board[30][30];   // 1: wall, 2: BBB, 1xx: Mxx, 2xx: Oxx
set<int> vis;        // 所有已经访问过的状态
set<int> ans;        // 状态的低18位，与在地图上的位置无关
int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};
 
bool check(int b) {  // 检查棋盘状态是否胜利
    int c[3][3];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            c[i][j] = b & 3;
            b = b >> 2;
        }
    }
    for (int i = 0; i < 3; i++) {
        if (c[i][0] == 1 && c[i][1] == 2 && c[i][2] == 2) return true;
        if (c[i][0] == 2 && c[i][1] == 2 && c[i][2] == 1) return true;
        if (c[0][i] == 1 && c[1][i] == 2 && c[2][i] == 2) return true;
        if (c[0][i] == 2 && c[1][i] == 2 && c[2][i] == 1) return true;
    }
    if (c[0][0] == 1 && c[1][1] == 2 && c[2][2] == 2) return true;
    if (c[0][0] == 2 && c[1][1] == 2 && c[2][2] == 1) return true;
    if (c[2][0] == 1 && c[1][1] == 2 && c[0][2] == 2) return true;
    if (c[2][0] == 2 && c[1][1] == 2 && c[0][2] == 1) return true;
    return false;
}
 
void dfs(int x) {   // x是状态，低28个二进制位有效
    if (vis.count(x)) return;
    vis.insert(x);
    if (check(x & 0x3FFFF)) {
        ans.insert(x & 0x3FFFF);
        return;
    }
    int r = x >> 23;
    int c = (x >> 18) & 0x1F;
    for (int i = 0; i < 4; i++) {            // 四个方向
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue; // 边界
        if (board[nr][nc] == 1) continue;    // 墙
        int nb = x & 0x3FFFF;                // 棋盘状态
        if (board[nr][nc] > 1) {             // 纸条位置，更新棋盘状态
            int type = board[nr][nc] >> 16;
            int row = (board[nr][nc] >> 8) & 0xFF;
            int col = board[nr][nc] & 0xFF;
            int shift = ((row - 1) * 3 + col - 1) * 2;
            if (((nb >> shift) & 3) == 0)    // 对应棋盘位置为空，可以更新
                nb |= (type << shift); 
        }
        dfs((nr << 23) + (nc << 18) + nb);
    }
}
 
int main() {
    scanf("%d", &n);
    int x = 0;
    for (int i = 0; i < n; i++) {       // 读地图
        char s[100];
        scanf("%s", s);
        for (int j = 0; j < n; j++) {
            char c = s[j*3];
            if (c == '#')
                board[i][j] = 1;
            else if (c == 'M' || c == 'O') {
                // byte 2: 纸条类型，byte 1: 纸条行，byte 0: 纸条列
                board[i][j] = ((c == 'M' ? 1 : 2) << 16) + ((s[j*3+1]-'0') << 8) + (s[j*3+2]-'0');
            }
            if (c == 'B') 
                x = (i << 23) + (j << 18);   // 初始状态，位置在(i,j)，棋盘为空 
        }
    }
    dfs(x);
    printf("%d", ans.size());
 
    return 0;
}