Minimum Moves to Move a Box to Their Target Location

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

class Solution {
public:
    int minPushBox(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int bx, by, px, py, tx, ty;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'B') bx = i, by = j;
                if (grid[i][j] == 'S') px = i, py = j;
                if (grid[i][j] == 'T') tx = i, ty = j;
            }
        vector<vector<int>> dirs{{0,1},{0,-1},{1,0},{-1,0}};
        auto canReach = [&](int sx, int sy, int ex, int ey, int bx, int by) {
            vector<vector<bool>> vis(m, vector<bool>(n));
            queue<pair<int,int>> q;
            q.push({sx, sy});
            vis[sx][sy] = true;
            while (!q.empty()) {
                auto [x, y] = q.front(); q.pop();
                if (x == ex && y == ey) return true;
                for (auto& d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                        !vis[nx][ny] && grid[nx][ny] != '#' &&
                        !(nx == bx && ny == by)) {
                        vis[nx][ny] = true;
                        q.push({nx, ny});
                    }
                }
            }
            return false;
        };
        set<tuple<int,int,int,int>> vis;
        queue<tuple<int,int,int,int,int>> q;
        q.push({bx, by, px, py, 0});
        vis.insert({bx, by, px, py});
        while (!q.empty()) {
            auto [bx, by, px, py, moves] = q.front(); q.pop();
            if (bx == tx && by == ty) return moves;
            for (auto& d : dirs) {
                int nbx = bx + d[0], nby = by + d[1];
                int ppx = bx - d[0], ppy = by - d[1];
                if (nbx < 0 || nbx >= m || nby < 0 || nby >= n ||
                    grid[nbx][nby] == '#') continue;
                if (ppx < 0 || ppx >= m || ppy < 0 || ppy >= n ||
                    grid[ppx][ppy] == '#') continue;
                if (!canReach(px, py, ppx, ppy, bx, by)) continue;
                if (vis.count({nbx, nby, bx, by})) continue;
                vis.insert({nbx, nby, bx, by});
                q.push({nbx, nby, bx, by, moves + 1});
            }
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

func minPushBox(grid [][]byte) int {
    m, n := len(grid), len(grid[0])
    var bx, by, px, py, tx, ty int
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            switch grid[i][j] {
            case 'B':
                bx, by = i, j
            case 'S':
                px, py = i, j
            case 'T':
                tx, ty = i, j
            }
        }
    }
    dirs := [][]int{{0,1},{0,-1},{1,0},{-1,0}}
    canReach := func(sx, sy, ex, ey, bx, by int) bool {
        vis := make([][]bool, m)
        for i := range vis { vis[i] = make([]bool, n) }
        q := [][2]int{{sx, sy}}
        vis[sx][sy] = true
        for len(q) > 0 {
            x, y := q[0][0], q[0][1]
            q = q[1:]
            if x == ex && y == ey { return true }
            for _, d := range dirs {
                nx, ny := x+d[0], y+d[1]
                if nx >= 0 && nx < m && ny >= 0 && ny < n &&
                    !vis[nx][ny] && grid[nx][ny] != '#' &&
                    !(nx == bx && ny == by) {
                    vis[nx][ny] = true
                    q = append(q, [2]int{nx, ny})
                }
            }
        }
        return false
    }
    type state struct{ bx, by, px, py int }
    vis := map[state]bool{}
    q := []struct{ bx, by, px, py, moves int }{{bx, by, px, py, 0}}
    vis[state{bx, by, px, py}] = true
    for len(q) > 0 {
        s := q[0]; q = q[1:]
        if s.bx == tx && s.by == ty { return s.moves }
        for _, d := range dirs {
            nbx, nby := s.bx+d[0], s.by+d[1]
            ppx, ppy := s.bx-d[0], s.by-d[1]
            if nbx < 0 || nbx >= m || nby < 0 || nby >= n || grid[nbx][nby] == '#' { continue }
            if ppx < 0 || ppx >= m || ppy < 0 || ppy >= n || grid[ppx][ppy] == '#' { continue }
            if !canReach(s.px, s.py, ppx, ppy, s.bx, s.by) { continue }
            ns := state{nbx, nby, s.bx, s.by}
            if vis[ns] { continue }
            vis[ns] = true
            q = append(q, struct{ bx, by, px, py, moves int }{nbx, nby, s.bx, s.by, s.moves + 1})
        }
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Solution {
    public int minPushBox(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int bx = 0, by = 0, px = 0, py = 0, tx = 0, ty = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'B') { bx = i; by = j; }
                if (grid[i][j] == 'S') { px = i; py = j; }
                if (grid[i][j] == 'T') { tx = i; ty = j; }
            }
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        class State { int bx, by, px, py; State(int a, int b, int c, int d) { bx=a;by=b;px=c;py=d; } }
        Set<String> vis = new HashSet<>();
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{bx, by, px, py, 0});
        vis.add(bx + "," + by + "," + px + "," + py);
        while (!q.isEmpty()) {
            int[] s = q.poll();
            if (s[0] == tx && s[1] == ty) return s[4];
            for (int[] d : dirs) {
                int nbx = s[0] + d[0], nby = s[1] + d[1];
                int ppx = s[0] - d[0], ppy = s[1] - d[1];
                if (nbx < 0 || nbx >= m || nby < 0 || nby >= n || grid[nbx][nby] == '#') continue;
                if (ppx < 0 || ppx >= m || ppy < 0 || ppy >= n || grid[ppx][ppy] == '#') continue;
                if (!canReach(grid, s[2], s[3], ppx, ppy, s[0], s[1])) continue;
                String key = nbx + "," + nby + "," + s[0] + "," + s[1];
                if (vis.contains(key)) continue;
                vis.add(key);
                q.offer(new int[]{nbx, nby, s[0], s[1], s[4] + 1});
            }
        }
        return -1;
    }
    private boolean canReach(char[][] grid, int sx, int sy, int ex, int ey, int bx, int by) {
        int m = grid.length, n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{sx, sy});
        vis[sx][sy] = true;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        while (!q.isEmpty()) {
            int[] s = q.poll();
            if (s[0] == ex && s[1] == ey) return true;
            for (int[] d : dirs) {
                int nx = s[0] + d[0], ny = s[1] + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                    !vis[nx][ny] && grid[nx][ny] != '#' &&
                    !(nx == bx && ny == by)) {
                    vis[nx][ny] = true;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class Solution {
    fun minPushBox(grid: Array<CharArray>): Int {
        val m = grid.size
        val n = grid[0].size
        var bx = 0; var by = 0; var px = 0; var py = 0; var tx = 0; var ty = 0
        for (i in 0 until m)
            for (j in 0 until n) {
                when (grid[i][j]) {
                    'B' -> { bx = i; by = j }
                    'S' -> { px = i; py = j }
                    'T' -> { tx = i; ty = j }
                }
            }
        val dirs = arrayOf(intArrayOf(0,1), intArrayOf(0,-1), intArrayOf(1,0), intArrayOf(-1,0))
        data class State(val bx: Int, val by: Int, val px: Int, val py: Int)
        val vis = mutableSetOf<State>()
        val q = ArrayDeque<Pair<State, Int>>()
        q.add(State(bx, by, px, py) to 0)
        vis.add(State(bx, by, px, py))
        fun canReach(sx: Int, sy: Int, ex: Int, ey: Int, bx: Int, by: Int): Boolean {
            val vis2 = Array(m) { BooleanArray(n) }
            val q2 = ArrayDeque<Pair<Int, Int>>()
            q2.add(sx to sy)
            vis2[sx][sy] = true
            while (q2.isNotEmpty()) {
                val (x, y) = q2.removeFirst()
                if (x == ex && y == ey) return true
                for (d in dirs) {
                    val nx = x + d[0]; val ny = y + d[1]
                    if (nx in 0 until m && ny in 0 until n &&
                        !vis2[nx][ny] && grid[nx][ny] != '#' &&
                        !(nx == bx && ny == by)) {
                        vis2[nx][ny] = true
                        q2.add(nx to ny)
                    }
                }
            }
            return false
        }
        while (q.isNotEmpty()) {
            val (state, moves) = q.removeFirst()
            if (state.bx == tx && state.by == ty) return moves
            for (d in dirs) {
                val nbx = state.bx + d[0]; val nby = state.by + d[1]
                val ppx = state.bx - d[0]; val ppy = state.by - d[1]
                if (nbx !in 0 until m || nby !in 0 until n || grid[nbx][nby] == '#') continue
                if (ppx !in 0 until m || ppy !in 0 until n || grid[ppx][ppy] == '#') continue
                if (!canReach(state.px, state.py, ppx, ppy, state.bx, state.by)) continue
                val newState = State(nbx, nby, state.bx, state.by)
                if (newState in vis) continue
                vis.add(newState)
                q.add(newState to moves + 1)
            }
        }
        return -1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution:
    def minPushBox(self, grid: list[list[str]]) -> int:
        from collections import deque
        m, n = len(grid), len(grid[0])
        bx = by = px = py = tx = ty = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 'B': bx, by = i, j
                if grid[i][j] == 'S': px, py = i, j
                if grid[i][j] == 'T': tx, ty = i, j
        dirs = [(0,1),(0,-1),(1,0),(-1,0)]
        def can_reach(sx: int, sy: int, ex: int, ey: int, bx: int, by: int) -> bool:
            vis = [[False]*n for _ in range(m)]
            q = deque([(sx, sy)])
            vis[sx][sy] = True
            while q:
                x, y = q.popleft()
                if x == ex and y == ey: return True
                for dx, dy in dirs:
                    nx, ny = x+dx, y+dy
                    if 0<=nx<m and 0<=ny<n and not vis[nx][ny] and grid[nx][ny]!='#' and (nx!=bx or ny!=by):
                        vis[nx][ny] = True
                        q.append((nx, ny))
            return False
        vis = set()
        q = deque([(bx, by, px, py, 0)])
        vis.add((bx, by, px, py))
        while q:
            bx, by, px, py, moves = q.popleft()
            if bx == tx and by == ty: return moves
            for dx, dy in dirs:
                nbx, nby = bx+dx, by+dy
                ppx, ppy = bx-dx, by-dy
                if not (0<=nbx<m and 0<=nby<n and grid[nbx][nby]!='#'): continue
                if not (0<=ppx<m and 0<=ppy<n and grid[ppx][ppy]!='#'): continue
                if not can_reach(px, py, ppx, ppy, bx, by): continue
                if (nbx, nby, bx, by) in vis: continue
                vis.add((nbx, nby, bx, by))
                q.append((nbx, nby, bx, by, moves+1))
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

use std::collections::{HashSet, VecDeque};
impl Solution {
    pub fn min_push_box(grid: Vec<Vec<char>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let (mut bx, mut by, mut px, mut py, mut tx, mut ty) = (0,0,0,0,0,0);
        for i in 0..m {
            for j in 0..n {
                match grid[i][j] {
                    'B' => { bx = i; by = j; }
                    'S' => { px = i; py = j; }
                    'T' => { tx = i; ty = j; }
                    _ => {}
                }
            }
        }
        let dirs = [(0,1),(0,-1),(1,0),(-1,0)];
        let can_reach = |sx: usize, sy: usize, ex: usize, ey: usize, bx: usize, by: usize| -> bool {
            let mut vis = vec![vec![false; n]; m];
            let mut q = VecDeque::new();
            q.push_back((sx, sy));
            vis[sx][sy] = true;
            while let Some((x, y)) = q.pop_front() {
                if x == ex && y == ey { return true; }
                for &(dx, dy) in &dirs {
                    let nx = x as isize + dx;
                    let ny = y as isize + dy;
                    if nx >= 0 && nx < m as isize && ny >= 0 && ny < n as isize {
                        let nx = nx as usize;
                        let ny = ny as usize;
                        if !vis[nx][ny] && grid[nx][ny] != '#' && !(nx == bx && ny == by) {
                            vis[nx][ny] = true;
                            q.push_back((nx, ny));
                        }
                    }
                }
            }
            false
        };
        let mut vis = HashSet::new();
        let mut q = VecDeque::new();
        q.push_back((bx, by, px, py, 0));
        vis.insert((bx, by, px, py));
        while let Some((bx, by, px, py, moves)) = q.pop_front() {
            if bx == tx && by == ty { return moves as i32; }
            for &(dx, dy) in &dirs {
                let nbx = bx as isize + dx;
                let nby = by as isize + dy;
                let ppx = bx as isize - dx;
                let ppy = by as isize - dy;
                if nbx < 0 || nbx >= m as isize || nby < 0 || nby >= n as isize || grid[nbx as usize][nby as usize] == '#' { continue; }
                if ppx < 0 || ppx >= m as isize || ppy < 0 || ppy >= n as isize || grid[ppx as usize][ppy as usize] == '#' { continue; }
                if !can_reach(px, py, ppx as usize, ppy as usize, bx, by) { continue; }
                if vis.contains(&(nbx as usize, nby as usize, bx, by)) { continue; }
                vis.insert((nbx as usize, nby as usize, bx, by));
                q.push_back((nbx as usize, nby as usize, bx, by, moves+1));
            }
        }
        -1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
    minPushBox(grid: string[][]): number {
        const m = grid.length, n = grid[0].length;
        let bx = 0, by = 0, px = 0, py = 0, tx = 0, ty = 0;
        for (let i = 0; i < m; ++i)
            for (let j = 0; j < n; ++j) {
                if (grid[i][j] === 'B') { bx = i; by = j; }
                if (grid[i][j] === 'S') { px = i; py = j; }
                if (grid[i][j] === 'T') { tx = i; ty = j; }
            }
        const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
        function canReach(sx: number, sy: number, ex: number, ey: number, bx: number, by: number): boolean {
            const vis = Array.from({length: m}, () => Array(n).fill(false));
            const q: [number, number][] = [[sx, sy]];
            vis[sx][sy] = true;
            while (q.length) {
                const [x, y] = q.shift()!;
                if (x === ex && y === ey) return true;
                for (const [dx, dy] of dirs) {
                    const nx = x + dx, ny = y + dy;
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
                        !vis[nx][ny] && grid[nx][ny] !== '#' &&
                        !(nx === bx && ny === by)) {
                        vis[nx][ny] = true;
                        q.push([nx, ny]);
                    }
                }
            }
            return false;
        }
        const vis = new Set<string>();
        const q: [number, number, number, number, number][] = [[bx, by, px, py, 0]];
        vis.add(`${bx},${by},${px},${py}`);
        while (q.length) {
            const [bx, by, px, py, moves] = q.shift()!;
            if (bx === tx && by === ty) return moves;
            for (const [dx, dy] of dirs) {
                const nbx = bx + dx, nby = by + dy;
                const ppx = bx - dx, ppy = by - dy;
                if (nbx < 0 || nbx >= m || nby < 0 || nby >= n || grid[nbx][nby] === '#') continue;
                if (ppx < 0 || ppx >= m || ppy < 0 || ppy >= n || grid[ppx][ppy] === '#') continue;
                if (!canReach(px, py, ppx, ppy, bx, by)) continue;
                const key = `${nbx},${nby},${bx},${by}`;
                if (vis.has(key)) continue;
                vis.add(key);
                q.push([nbx, nby, bx, by, moves+1]);
            }
        }
        return -1;
    }
}