1263.推箱子

链接：1263.推箱子
难度：Hard
标签：广度优先搜索、数组、矩阵、堆（优先队列）
简介：返回将箱子推到目标位置的最小 推动 次数，如果无法做到，请返回 -1。

题解 1 - cpp

• 编辑时间：2023-05-08
• 执行用时：72ms
• 内存消耗：15.4MB
• 编程语言：cpp
• 解法介绍：dfs每次统计左右子树的差值。

#define X first
#define Y second
#define pii pair<int, int>
class UnionFind {
    public:
    int n;
    vector<int> data, cnt;
    UnionFind(int n) : n(n), data(vector<int>(n, 0)), cnt(vector<int>(n, 1)) {
        iota(data.begin(), data.end(), 0);
    }
    int size(int v) { return cnt[find(v)]; }
    int find(int v) {
        if (data[v] == v) return v;
        return data[v] = find(data[v]);
    }
    void uni(int v1, int v2) {
        int p1 = find(v1), p2 = find(v2);
        if (p1 != p2) cnt[p1] += cnt[p2], data[p2] = p1;
    }
    bool same(int v1, int v2) { return find(v1) == find(v2); }
};
int pos2Idx(int x, int y, int size) { return x * size + y; }
void idx2Pos(int idx, int size, int &x, int &y) {
    x = idx / size;
    y = idx % size;
}
vector<vector<int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// 记录箱子和人的位置
struct Node {
    pii p, b;
    Node(pii p, pii b): p(p), b(b) {}
};
class Solution {
public:
    int minPushBox(vector<vector<char>>& grid) {
        pii t, p, b;
        int n = grid.size(), m = grid[0].size();
        // 统计箱子和人的位置放置重复计算
        unordered_map<int, unordered_map<int, bool>> used;
        // 判断两个坐标是否相等
        auto is_same = [&](pii a, pii b) -> bool {
            return a.X == b.X && a.Y == b.Y;
        };
        // 针对当前Node值，计算并查集，计算时要排除箱子位置，用于后面判断人是不是能到这个点
        auto get_uf = [&](Node cur) -> UnionFind {
            UnionFind uf(n * m);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == '.' && !is_same(cur.b, make_pair(i, j))) {
                        for (int k = 0; k < 4; k++) {
                            int ni = i + dirs[k][0], nj = j + dirs[k][1];
                            if (0 <= ni && ni < n && 0 <= nj && nj < m && grid[ni][nj] == '.' && !is_same(cur.b, make_pair(ni, nj))) {
                                uf.uni(pos2Idx(i, j, m), pos2Idx(ni, nj, m));
                            }
                        }
                    }
                }
            }
            return uf;
        };
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 'T') t = make_pair(i, j), grid[i][j] = '.';
                else if (grid[i][j] == 'B') b = make_pair(i, j), grid[i][j] = '.';
                else if (grid[i][j] == 'S') p = make_pair(i, j), grid[i][j] = '.';
            }
        }
        queue<Node> q;
        q.push(Node(p, b));
        int size = 1, step = 0;
        while (q.size()) {
            auto cur = q.front();
            q.pop();
            if (is_same(cur.b, t)) return step;
            auto uf = get_uf(cur);
            for (int k = 0; k < 4; k++) {
                int ni = cur.b.X + dirs[k][0], nj = cur.b.Y + dirs[k][1],
                    bi = cur.b.X - dirs[k][0], bj = cur.b.Y - dirs[k][1];
                // 如果箱子要推到(ni, nj), 那么人要在(bi, bj)位置上推，所以这两个位置都要空，且这个位置没有被统计过
                if (0 <= ni && ni < n && 0 <= nj && nj < m && grid[ni][nj] == '.' &&
                    0 <= bi && bi < n && 0 <= bj && bj < m && grid[bi][bj] == '.' &&
                    uf.same(pos2Idx(cur.p.X, cur.p.Y, m), pos2Idx(bi, bj, m)) &&
                    !used[pos2Idx(cur.b.X, cur.b.Y, m)][pos2Idx(ni, nj, m)]) {
                    q.push(Node(make_pair(cur.b.X, cur.b.Y), make_pair(ni, nj)));
                    used[pos2Idx(cur.b.X, cur.b.Y, m)][pos2Idx(ni, nj, m)] = true;
                }
            }
            if (--size == 0) {
                size = q.size();
                step++;
            }
        }
        return -1;
    }
};

题解 2 - python

• 编辑时间：2023-05-09
• 执行用时：2080ms
• 内存消耗：16.5MB
• 编程语言：python
• 解法介绍：同上。

dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
class UnionFind:
    def __init__(self, n) -> None:
        self.n = n
        self.data = [i for i in range(0, n)]
        self.cnt = [1] * n
    def size(self, v: int) -> int:
        return self.cnt[self.find(v)]
    def find(self, v: int) -> int:
        if self.data[v] != v:
            self.data[v] = self.find(self.data[v])
        return self.data[v]
    def uni(self, v1: int, v2: int):
        p1 = self.find(v1)
        p2 = self.find(v2)
        if p1 != p2:
            self.cnt[p1] += self.cnt[p2]
            self.data[p2] = p1
    def same(self, v1: int, v2: int):
        return self.find(v1) == self.find(v2)

def pos2Idx(x: int, y: int, size: int):
    return x * size + y

def idx2pox(idx: int, size: int) -> Tuple[int,  int]:
    return (idx // size, idx % size)
class Node:
    def __init__(self, p: Tuple[int, int], b: Tuple[int, int]) -> None:
        self.p = p
        self.b = b
class Solution:
    def minPushBox(self, grid: List[List[str]]) -> int:
        t, p, b = (0, 0), (0, 0), (0, 0)
        n = len(grid)
        m = len(grid[0])
        used = defaultdict(dict)
        def is_valid(v: Tuple[int, int]) -> bool:
            return 0 <= v[0] < n and 0 <= v[1] < m
        def is_same(a: Tuple[int, int], b: Tuple[int, int]):
            return a[0] == b[0] and a[1] == b[1]
        def get_uf(cur: Node) -> UnionFind:
            uf = UnionFind(n * m)
            for i in range(n):
                for j in range(m):
                    if grid[i][j] == '.' and not is_same(cur.b, (i, j)):
                        for k in range(4):
                            ni = i + dirs[k][0]
                            nj = j + dirs[k][1]
                            if is_valid((ni, nj)) and grid[ni][nj] == '.' and not is_same(cur.b, (ni, nj)):
                                uf.uni(pos2Idx(i, j, m), pos2Idx(ni, nj, m))
            return uf
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 'T':
                    t = (i, j)
                    grid[i][j] = '.'
                elif grid[i][j] == 'B':
                    b = (i, j)
                    grid[i][j] = '.'
                elif grid[i][j] == 'S':
                    p = (i, j)
                    grid[i][j] = '.'
        q = deque()
        q.append(Node(p, b))
        size = 1
        step = 0
        while len(q):
            cur: Node = q.popleft()
            if is_same(cur.b, t):
                return step
            uf = get_uf(cur)
            for k in range(4):
                ni = cur.b[0] + dirs[k][0]
                nj = cur.b[1] + dirs[k][1]
                bi = cur.b[0] - dirs[k][0]
                bj = cur.b[1] - dirs[k][1]
                pidx = pos2Idx(cur.p[0], cur.p[1], m)
                bidx = pos2Idx(cur.b[0], cur.b[1], m)
                if is_valid((ni, nj)) and grid[ni][nj] == '.' and is_valid((bi, bj)) and grid[bi][bj] == '.' and uf.same(pidx, pos2Idx(bi, bj, m)) and pos2Idx(ni, nj, m) not in used[bidx]:
                    q.append(Node(cur.b, (ni, nj)))
                    used[bidx][pos2Idx(ni, nj, m)] = True
            size -= 1
            if size == 0:
                size = len(q)
                step += 1
        return -1

题解 3 - rust

• 编辑时间：2023-05-09
• 执行用时：16ms
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

pub use std::collections::HashMap;
pub use std::collections::VecDeque;
pub const dirs: [[i32; 2]; 4] = [[0, 1], [0, -1], [1, 0], [-1, 0]];
pub struct UnionFind {
    n: usize,
    data: Vec<usize>,
    cnt: Vec<usize>,
}
impl UnionFind {
    pub fn new(n: usize) -> Self {
        let mut data = vec![0; n];
        for i in 0..data.len() {
            data[i] = i;
        }
        Self {
            n,
            data,
            cnt: vec![0; n],
        }
    }
    pub fn size(&mut self, v: usize) -> usize {
        let idx = self.find(v);
        self.cnt[idx]
    }
    pub fn find(&mut self, v: usize) -> usize {
        if self.data[v] != v {
            self.data[v] = self.find(self.data[v]);
        }
        self.data[v]
    }
    pub fn uni(&mut self, v1: usize, v2: usize) {
        let p1 = self.find(v1);
        let p2 = self.find(v2);
        if p1 != p2 {
            self.cnt[p1] += self.cnt[p2];
            self.data[p2] = p1;
        }
    }
    pub fn same(&mut self, v1: usize, v2: usize) -> bool {
        self.find(v1) == self.find(v2)
    }
}
pub fn pos2Idx(x: usize, y: usize, size: usize) -> usize {
    x * size + y
}
pub fn idx2Pos(idx: usize, size: usize) -> (usize, usize) {
    (idx / size, idx % size)
}
type Position = (usize, usize);
#[derive(Clone, Copy, Debug)]
struct Node {
    p: Position,
    b: Position,
}
impl Node {
    fn new(p: Position, b: Position) -> Self {
        Self { p, b }
    }
}
impl Solution {
    pub fn min_push_box(mut grid: Vec<Vec<char>>) -> i32 {
        let mut p: Position = (0, 0);
        let mut b: Position = (0, 0);
        let mut t: Position = (0, 0);
        let n = grid.len();
        let m = grid[0].len();
        let mut used = HashMap::<usize, HashMap<usize, bool>>::new();
        let is_same = |a: Position, b: Position| a.0 == b.0 && a.1 == b.1;
        let is_valid = |v: (i32, i32)| 0 <= v.0 && v.0 < n as i32 && 0 <= v.1 && v.1 < m as i32;
        let get_uf = |grid: &Vec<Vec<char>>, cur: Node| {
            let mut uf = UnionFind::new(n * m);
            for i in 0..n {
                for j in 0..m {
                    if grid[i][j] == '.' && !is_same(cur.b, (i, j)) {
                        for k in 0..4 {
                            let ni = i as i32 + dirs[k][0];
                            let nj = j as i32 + dirs[k][1];
                            if is_valid((ni, nj))
                                && grid[ni as usize][nj as usize] == '.'
                                && !is_same(cur.b, (ni as usize, nj as usize))
                            {
                                uf.uni(pos2Idx(i, j, m), pos2Idx(ni as usize, nj as usize, m));
                            }
                        }
                    }
                }
            }
            uf
        };
        for i in 0..n {
            for j in 0..m {
                let t1 = grid[i][j] == 'T';
                let t2 = grid[i][j] == 'B';
                let t3 = grid[i][j] == 'S';
                if t1 {
                    t = (i, j);
                    grid[i][j] = '.';
                } else if t2 {
                    b = (i, j);
                    grid[i][j] = '.';
                } else if t3 {
                    p = (i, j);
                    grid[i][j] = '.';
                }
            }
        }
        let mut q = VecDeque::<Node>::new();
        q.push_back(Node::new(p, b));
        let mut size = 1;
        let mut step = 0;
        while let Some(cur) = q.pop_front() {
            if is_same(cur.b, t) {
                return step;
            }
            let mut uf = get_uf(&grid, cur);
            for k in 0..4 {
                let ni = cur.b.0 as i32 + dirs[k][0];
                let nj = cur.b.1 as i32 + dirs[k][1];
                let bi = cur.b.0 as i32 - dirs[k][0];
                let bj = cur.b.1 as i32 - dirs[k][1];
                let pidx = pos2Idx(cur.p.0, cur.p.1, m);
                let bidx = pos2Idx(cur.b.0, cur.b.1, m);
                if is_valid((ni, nj))
                    && grid[ni as usize][nj as usize] == '.'
                    && is_valid((bi, bj))
                    && grid[bi as usize][bj as usize] == '.'
                    && uf.same(pidx, pos2Idx(bi as usize, bj as usize, m))
                {
                    if used.contains_key(&bidx)
                        && used.get(&bidx).unwrap().contains_key(&pos2Idx(
                            ni as usize,
                            nj as usize,
                            m,
                        ))
                    {
                        continue;
                    }
                    let ni = ni as usize;
                    let nj = nj as usize;
                    q.push_back(Node::new(cur.b, (ni, nj)));
                    let item = used.entry(bidx).or_insert(HashMap::new());
                    *item.entry(pos2Idx(ni, nj, m)).or_insert(false) = true;
                }
            }
            size -= 1;
            if size == 0 {
                size = q.len();
                step += 1;
            }
        }
        -1
    }
}