1263. 推箱子 - Kotlin 两层BFS

Smile_slime_47
  2023-05-08 2023-05-08 Created  

原题地址：https://leetcode.cn/problems/minimum-moves-to-move-a-box-to-their-target-location/

题解

基本思路是两层BFS：对箱子进行BFS搜索，每次判断箱子要移动到一个位置时对人当前位置再次进行BFS，判断人是否能够达到推动箱子的位置

除了维护一个Bskip和Sskip外，还要维护一个avoid数组，记录下人无法前往的位置，除了地图中的”#”外，还有当前箱子的位置也属于障碍物，对人BFS时要在不经过#和B的情况下达到推动箱子的位置

在箱子移动时，不能只根据箱子的skip来判断是否重复，因为存在一种可能性：第一次箱子经过该点时和这次经过该点的人的位置在箱子的不同两侧，这可能导致这次箱子再次经过该点时由于人的位置的不同而可以前往第一次经过时不能前往的点，因此要同时根据Bskip和Sskip判断

除去对人的BFS外，本题整体上是一个层次遍历，最后返回达到”T”时的最小层次即可

考虑到数据范围只有20x20，这种暴力一般的搜索竟然是真的可行的（

时间复杂度：O(N^2)

空间复杂度：O(N^2)

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
class Solution {
    var reach=false
    fun minPushBox(grid: Array<CharArray>): Int {
        var Bskip=Array(grid.size){Array(grid[0].size){false}}
        var Sskip=Array(grid.size){Array(grid[0].size){false}}
        var avoid=Array(grid.size){Array(grid[0].size){false}}
        var BBFS = LinkedList<Pair<Int,Int>>()
        var SPOS = LinkedList<Pair<Int,Int>>()
        var tmp:Pair<Int,Int>
        var rB:Int
        var cB:Int
        var rS:Int
        var cS:Int
        var cnt:Int=0
        var step:Int=0
        var min=99999

        for(r in 0 until grid.size){
            for(c in 0 until grid[0].size){
                if(grid[r][c]=='B'){
                    BBFS.addLast(Pair(r,c))
                    Bskip[r][c]=true
                }
                if(grid[r][c]=='S'){
                    SPOS.addLast(Pair(r,c))
                    Sskip[r][c]=true
                }
                if(grid[r][c]=='#'){
                    Bskip[r][c]=true
                    Sskip[r][c]=true
                    avoid[r][c]=true
                }
            }
        }

        while (BBFS.isNotEmpty()){
            cnt=BBFS.size
            while (cnt>0){
                tmp=BBFS.removeAt(0)
                rB=tmp.first
                cB=tmp.second
                tmp=SPOS.removeAt(0)
                rS=tmp.first
                cS=tmp.second
                avoid[rB][cB]=true

                if(grid[rB][cB]=='T'){
                    reach=true
                    min=if(min<step) min else step
                    break
                }

                if(rB>0&&rB<grid.size-1&&!avoid[rB-1][cB]&&(!Bskip[rB-1][cB]||!Sskip[rB+1][cB])&&canReach(grid,avoid,rS,cS,rB+1,cB)){
                    BBFS.addLast(Pair(rB-1,cB))
                    SPOS.addLast(Pair(rB+1,cB))
                    Bskip[rB-1][cB]=true
                    Sskip[rB+1][cB]=true
                }
                if(rB>0&&rB<grid.size-1&&!avoid[rB+1][cB]&&(!Bskip[rB+1][cB]||!Sskip[rB-1][cB])&&canReach(grid,avoid,rS,cS,rB-1,cB)){
                    BBFS.addLast(Pair(rB+1,cB))
                    SPOS.addLast(Pair(rB-1,cB))
                    Bskip[rB+1][cB]=true
                    Sskip[rB-1][cB]=true
                }
                if(cB>0&&cB<grid[0].size-1&&!avoid[rB][cB-1]&&(!Bskip[rB][cB-1]||!Sskip[rB][cB+1])&&canReach(grid,avoid,rS,cS,rB,cB+1)){
                    BBFS.addLast(Pair(rB,cB-1))
                    SPOS.addLast(Pair(rB,cB+1))
                    Bskip[rB][cB-1]=true
                    Sskip[rB][cB+1]=true
                }
                if(cB>0&&cB<grid[0].size-1&&!avoid[rB][cB+1]&&(!Bskip[rB][cB+1]||!Sskip[rB][cB-1])&&canReach(grid,avoid,rS,cS,rB,cB-1)){
                    BBFS.addLast(Pair(rB,cB+1))
                    SPOS.addLast(Pair(rB,cB-1))
                    Bskip[rB][cB+1]=true
                    Sskip[rB][cB-1]=true
                }
                avoid[rB][cB]=false
                cnt--
            }
            step++
        }
        return if(reach) min else -1
    }
}

fun canReach(grid: Array<CharArray>,skip:Array<Array<Boolean>>,r:Int,c:Int,tr:Int,tc:Int):Boolean{
    if(tr<0||tc<0||tr>=grid.size||tc>=grid[0].size||skip[tr][tc]){
        return false
    }

    var SBFS = LinkedList<Pair<Int,Int>>()
    var funSkip=Array(grid.size){Array(grid[0].size){false}}
    for(i in 0 until skip.size){
        for(j in 0 until skip[0].size){
            funSkip[i][j]=skip[i][j]
        }
    }
    SBFS.addLast(Pair(r,c))
    funSkip[r][c]=true
    var rNow:Int
    var cNow:Int
    var tmp:Pair<Int,Int>
    while (SBFS.isNotEmpty()){
        tmp=SBFS.removeFirst()
        rNow=tmp.first
        cNow=tmp.second
        if(rNow==tr&&cNow==tc)return true
        if(rNow>0&&!funSkip[rNow-1][cNow]){
            SBFS.addLast(Pair(rNow-1,cNow))
            funSkip[rNow-1][cNow]=true
        }
        if(rNow<grid.size-1&&!funSkip[rNow+1][cNow]){
            SBFS.addLast(Pair(rNow+1,cNow))
            funSkip[rNow+1][cNow]=true
        }
        if(cNow>0&&!funSkip[rNow][cNow-1]){
            SBFS.addLast(Pair(rNow,cNow-1))
            funSkip[rNow][cNow-1]=true
        }
        if(cNow<grid[0].size-1&&!funSkip[rNow][cNow+1]){
            SBFS.addLast(Pair(rNow,cNow+1))
            funSkip[rNow][cNow+1]=true
        }
    }
    return false;
}
Comments
On this page
1263. 推箱子 - Kotlin 两层BFS
  1. 题解