2022-5-17 推箱子(未解决)

「推箱子」是一款风靡全球的益智小游戏，玩家需要将箱子推到仓库中的目标位置。

游戏地图用大小为 m x n 的网格 grid 表示，其中每个元素可以是墙、地板或者是箱子。

现在你将作为玩家参与游戏，按规则将箱子 'B' 移动到目标位置 'T' ：

玩家用字符 'S' 表示，只要他在地板上，就可以在网格中向上、下、左、右四个方向移动。
地板用字符 '.' 表示，意味着可以自由行走。
墙用字符 '#' 表示，意味着障碍物，不能通行。
箱子仅有一个，用字符 'B' 表示。相应地，网格上有一个目标位置 'T'。
玩家需要站在箱子旁边，然后沿着箱子的方向进行移动，此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
玩家无法越过箱子。
返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。

示例 1：
输入：grid = [["#","#","#","#","#","#"],
             ["#","T","#","#","#","#"],
             ["#",".",".","B",".","#"],
             ["#",".","#","#",".","#"],
             ["#",".",".",".","S","#"],
             ["#","#","#","#","#","#"]]
输出：3
解释：我们只需要返回推箱子的次数。
示例 2：
输入：grid = [["#","#","#","#","#","#"],
             ["#","T","#","#","#","#"],
             ["#",".",".","B",".","#"],
             ["#","#","#","#",".","#"],
             ["#",".",".",".","S","#"],
             ["#","#","#","#","#","#"]]
输出：-1
示例 3：
输入：grid = [["#","#","#","#","#","#"],
             ["#","T",".",".","#","#"],
             ["#",".","#","B",".","#"],
             ["#",".",".",".",".","#"],
             ["#",".",".",".","S","#"],
             ["#","#","#","#","#","#"]]
输出：5
解释：向下、向左、向左、向上再向上。

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 20
• grid 仅包含字符 '.', '#', 'S' , 'T', 以及 'B'。
• grid 中 'S', 'B' 和 'T' 各只能出现一个。

以下示例答案为8，输出结果为INT_MAX，代码待修正。

#include 

#define N 20
#pragma GCC optimize(2)

int xMax, yMax, xTarget, yTarget, minMove;

using namespace std;

const int DIR[4][2]{{-1, 0},
                    {1,  0},
                    {0,  -1},
                    {0,  1}};

bool visited[N][N][4]{false};

bool isObstacle(const vector> &grid, int x, int y) {
    return x < 0 || y < 0 || x >= xMax || y >= yMax || grid[x][y] != '.';
}

bool isAccessible(vector> &grid, int xStart, int yStart, int xEnd, int yEnd) {
    if (isObstacle(grid, xEnd, yEnd)) { return false; }
    if (xStart == xEnd && yStart == yEnd) { return true; }
    for (int i = 0, dx, dy; i < 4; i++) {
        dx = DIR[i][0], dy = DIR[i][1];
        if (!isObstacle(grid, xStart + dx, yStart + dy)) {
            char prev = grid[xStart][yStart];
            grid[xStart][yStart] = 'V';
            if (isAccessible(grid, xStart + dx, yStart + dy, xEnd, yEnd)) {
                grid[xStart][yStart] = prev;
                return true;
            }
            grid[xStart][yStart] = prev;
        }
    }
    return false;
}

tuple convertGrid(vector> &grid) {
    int xHuman, yHuman, xBox, yBox;
    for (int i = 0; i < xMax; i++) {
        for (int j = 0; j < yMax; j++) {
            if (grid[i][j] == 'B') { xBox = i, yBox = j; }
            if (grid[i][j] == 'S') { xHuman = i, yHuman = j, grid[i][j] = '.'; }
            if (grid[i][j] == 'T') { xTarget = i, yTarget = j, grid[i][j] = '.'; }
        }
    }
    return tuple{xHuman, yHuman, xBox, yBox};
}

void bfs(vector> &grid, int nMove, int iBox, int jBox, int iHuman, int jHuman) {
    if (iBox == xTarget && jBox == yTarget) {
        minMove = min(minMove, nMove);
        return;
    }
    for (int i = 0, dx, dy; i < 4; i++) {
        if (visited[iBox][jBox][i]) continue; // 状态已访问
        visited[iBox][jBox][i] = true; // 访问该状态
        dx = DIR[i][0], dy = DIR[i][1];
        if (isObstacle(grid, iBox + dx, jBox + dy)) continue; // 下一位置为障碍点
        if (!isAccessible(grid, iHuman, jHuman, iBox - dx, jBox - dy)) continue; // 推动箱子的位置不可到达
        grid[iBox][jBox] = '.', grid[iBox + dx][jBox + dy] = 'B';
        bfs(grid, nMove + 1, iBox + dx, jBox + dy, iBox - dx, jBox - dy);
        grid[iBox][jBox] = 'B', grid[iBox + dx][jBox + dy] = '.';
    }
}

int main() {
    vector> grid{{'#', '.', '.', '#', 'T', '#', '#', '#', '#'},
                              {'#', '.', '.', '#', '.', '#', '.', '.', '#'},
                              {'#', '.', '.', '#', '.', '#', 'B', '.', '#'},
                              {'#', '.', '.', '.', '.', '.', '.', '.', '#'},
                              {'#', '.', '.', '.', '.', '#', '.', 'S', '#'},
                              {'#', '.', '.', '#', '.', '#', '#', '#', '#'}};
    xMax = grid.size(), yMax = grid[0].size();
    int xHuman, yHuman, xBox, yBox;
    minMove = INT_MAX;
    tie(xHuman, yHuman, xBox, yBox) = convertGrid(grid);
    bfs(grid, 0, xBox, yBox, xHuman, yHuman);
    cout << minMove;
    return 0;
}

#include 

#pragma GCC optimize(2)

using namespace std;

int step[1 << 20];
int n, m;
int dir[4][2]{{0,  1},
              {1,  0},
              {0,  -1},
              {-1, 0}};

bool isValid(const vector> &grid, int x, int y) {
    return x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != '#';
}

int pack(int xStart, int yStart, int xBox, int yBox) {
    return (xStart << 15) | (yStart << 10) | (xBox << 5) | yBox;
}

tuple unPack(int val) {
    return {val >> 15 & 31, val >> 10 & 31, val >> 5 & 31, val & 31};
}


int minPushBox(vector> &grid) {
    m = grid.size(), n = grid[0].size();
    memset(step, -1, sizeof(step));
    int xStart, yStart, xBox, yBox;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 'S') { xStart = i, yStart = j, grid[i][j] = '.'; }
            if (grid[i][j] == 'B') { xBox = i, yBox = j, grid[i][j] = '.'; }
        }
    }
    queue que;
    int packValue = pack(xStart, yStart, xBox, yBox);
    int ans = -1;
    int xStartNext, yStartNext, xBoxNext, yBoxNext, packValueNext;
    step[packValue] = 0;
    que.push(packValue);
    while (!que.empty()) {
        packValue = que.front();
        que.pop();
        tie(xStart, yStart, xBox, yBox) = unPack(packValue);
        if (grid[xBox][yBox] == 'T') {
            if (ans == -1 || step[packValue] < ans) ans = step[packValue];
            continue;
        }
        for (auto &i : dir) {
            xStartNext = xStart + i[0];
            yStartNext = yStart + i[1];
            if (!isValid(grid, xStartNext, yStartNext)) continue;
            if (xStartNext == xBox && yStartNext == yBox) {
                xBoxNext = xBox + i[0];
                yBoxNext = yBox + i[1];
                if (!isValid(grid, xBoxNext, yBoxNext)) continue;
                packValueNext = pack(xStartNext, yStartNext, xBoxNext, yBoxNext);
                if (step[packValueNext] == -1 || step[packValueNext] + 1 < step[packValue]) {
                    step[packValueNext] = step[packValue] + 1;
                    que.push(packValueNext);
                }
            } else {
                packValueNext = pack(xStartNext, yStartNext, xBox, yBox);
                if (step[packValueNext] == -1 || step[packValueNext] < step[packValue]) {
                    step[packValueNext] = step[packValue];
                    que.push(packValueNext);
                }
            }
        }
    }
    return ans;
}


int main() {
    vector> grid{{'.', '.', '#', '.', '.', '.', '.', '#'},
                              {'.', 'B', '.', '.', '.', '.', '.', '#'},
                              {'.', '.', 'S', '.', '.', '.', '.', '.'},
                              {'.', '#', '.', '.', '.', '.', '.', '.'},
                              {'.', '.', '.', '.', '.', '.', '.', '.'},
                              {'.', '.', '.', 'T', '.', '.', '.', '.'},
                              {'.', '.', '.', '.', '.', '.', '.', '#'},
                              {'.', '#', '.', '.', '.', '.', '.', '.'}};
    cout << minPushBox(grid);
    return 0;
}