【拉箱子——模拟+DFS】

题目

代码

#include <bits/stdc++.h>
using namespace std;
map<vector<vector<int>>, int> check;
vector<vector<int>> mp;
int n, m, ans;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void dfs(vector<vector<int>> tmp, int ax, int ay, int bx, int by, int cx, int cy)
{
    if (ax == bx && ay == by) // 处理人箱重叠的情况（这里不能推箱子）
    {
        for (int k = 0; k < 4; k++) // 人移动
        {
            int tx = ax + dx[k];
            int ty = ay + dy[k];
            if (tx < 0 || ty < 0 || tx >= n || ty >= m || tmp[tx][ty] == 1) // 边界和墙判断
                continue;
            tmp[ax][ay] -= 1 << 1, tmp[tx][ty] += 1 << 1;
            dfs(tmp, tx, ty, bx, by, cx, cy);
            tmp[ax][ay] += 1 << 1, tmp[tx][ty] -= 1 << 1;
        }
        return;
    }

    if (check.count(tmp))
        return; // 判断状态是否考虑过
    if (!(bx == cx && by == cy) && !(ax == cx && ay == cy))
        ans++; // 没考虑过且符合要求（放在这里是要借助前面的人箱不重叠条件，但是实测放在最前也可以）
    check[tmp] = 1;

    for (int k = 0; k < 4; k++) // 到这里，就说明出现人终重叠或者是箱终重叠，考虑人移动和推箱子来解决
    {
        int tx = ax + dx[k]; // 人移动
        int ty = ay + dy[k];
        if (tx < 0 || ty < 0 || tx >= n || ty >= m || tmp[tx][ty] == 1)
            continue;
        if (tx != bx || ty != by) // 人没移动到箱子上
        {
            tmp[ax][ay] -= 1 << 1, tmp[tx][ty] += 1 << 1;
            dfs(tmp, tx, ty, bx, by, cx, cy);
            tmp[ax][ay] += 1 << 1, tmp[tx][ty] -= 1 << 1;
        }
        int ttx = bx + dx[k];
        int tty = by + dy[k];
        if (tx == bx && ty == by && ttx >= 0 && ttx < n && tty >= 0 && tty < m && tmp[ttx][tty] != 1)
        { // 人移动的目的地是箱子的起始地
            tmp[ax][ay] -= 1 << 1, tmp[tx][ty] += 1 << 1;
            tmp[bx][by] -= 1 << 2, tmp[ttx][tty] += 1 << 2;
            dfs(tmp, tx, ty, ttx, tty, cx, cy);
            tmp[ax][ay] += 1 << 1, tmp[tx][ty] -= 1 << 1;
            tmp[bx][by] += 1 << 2, tmp[ttx][tty] -= 1 << 2;
        }
    }
}
int main()
{
    cin >> n >> m;
    mp = vector<vector<int>>(n, vector<int>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> mp[i][j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (mp[i][j] == 0)
            {
                mp[i][j] = (1 << 1) + (1 << 2) + (1 << 3);
                dfs(mp, i, j, i, j, i, j);
                mp[i][j] = 0;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}