题目

代码

#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;
}