推箱子之BFS

发表于 | 分类于 | 阅读次数

题目

给出起点，给出箱子的位置，给出目的地，求最少需要多少步能够将箱子推到目的地；如果不存在，返回-1，如下图所示：

txz2

转化为字符如下：

1
2
3
4
5
6
7
{'#','#','#','#','#','#','#','#','#','#','#'},
{'#','E','#','#','.','.','.','.','.','.','#'},
{'#','.','#','.','#','.','.','#','#','#','#'},
{'#','.','.','.','.','O','.','.','.','.','#'},
{'#','.','#','#','#','#','#','#','.','.','#'},
{'#','.','.','.','.','.','S','.','.','.','#'},
{'#','#','#','#','#','#','#','#','#','#','#'}

分析

今日头条校招笔试中的一道题，比实习笔试复杂太多，花了我一下午的时间（3个多小时）才写出来，使用BFS+BFS，代码比较复杂，没有简化；本意是熟悉BFS，关于BFS的输出问题，后期会补上

这道题和我之前见到的自走迷宫有点像，自走迷宫是纯粹的BFS，这道题还需要转化一下；
当然和DFS一样肯定会重复，而用DP解决，这里先不谈这个；

以箱子为分析的重点，每次箱子可以向上右下左这四个方向移动，假设此时箱子需要向上移动，那么人先需要从前一个位置移动箱子下面的位置，才能把箱子向上推动
这里出现了一个子问题：从前一个位置移动到箱子下面的位置的最短路径，这是子BFS
主BFS如下：
每次判断箱子是否可以向指定方向移动，如果可以，则用队列将箱子移动后的点存储下来，把此时人得位置存储下来，把此时总共走得步数存储下来；
如果队列不为空，找到队列左边的点的步数小于min值的点来继续分析，如果该点等于目的点，将该点得步数替换min，继续找步数小于min的点分析，知道队列为空，返回-1或min；

代码

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
/**
 * 初始化flag，并分别计算人从起点到箱子的上右下左的位置后，推动箱子的情况，然后找出最小的步数
 * @param a 初始矩阵
 * @param n 行
 * @param m 列
 * @return 最短路径长
 */
public static int bfsStart(char[][]a,int n,int m){
    int si,sj,oi,oj,ei,ej;
    int min=Integer.MAX_VALUE;
    int temp1,temp2;
    si=sj=oi=oj=ei=ej=0;
    temp2=-1;
    boolean[][]flag=new boolean[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]=='O') {
                oi = i;
                oj = j;
            }else if(a[i][j]=='S'){
                si=i;
                sj=j;
            }else if(a[i][j]=='E'){
                ei=i;
                ej=j;
            }else if(a[i][j]=='#')flag[i][j]=true;
        }
    }
    if(oi-1>=0){
        if(!flag[oi-1][oj]){
            flag[oi][oj]=true;
            temp1=bfs(flag,n,m,si,sj,oi-1,oj);
            if(temp1!=-1)temp2=bfs1(flag,n,m,oi,oj,ei,ej,1);
            if(temp2!=-1)min=min>temp1+temp2?temp1+temp2:min;
            flag[oi][oj]=false;
            temp2=-1;
        }
    }
    if(oj+1<m){
        if(!flag[oi][oj+1]){
            flag[oi][oj]=true;
            temp1=bfs(flag,n,m,si,sj,oi,oj+1);
            if(temp1!=-1)temp2=bfs1(flag,n,m,oi,oj,ei,ej,2);
            if(temp2!=-1)min=min>temp1+temp2?temp1+temp2:min;
            flag[oi][oj]=false;
            temp2=-1;
        }
    }
    if(oi+1<n){
        if(!flag[oi+1][oj]){
            flag[oi][oj]=true;
            temp1=bfs(flag,n,m,si,sj,oi+1,oj);
            if(temp1!=-1)temp2=bfs1(flag,n,m,oi,oj,ei,ej,3);
            if(temp2!=-1)min=min>temp1+temp2?temp1+temp2:min;
            flag[oi][oj]=false;
            temp2=-1;
        }
    }
    if(oj-1>=0){
        if(!flag[oi][oj-1]){
            flag[oi][oj]=true;
            temp1=bfs(flag,n,m,si,sj,oi,oj-1);
            if(temp1!=-1)temp2=bfs1(flag,n,m,oi,oj,ei,ej,4);
            if(temp2!=-1)min=min>temp1+temp2?temp1+temp2:min;
            flag[oi][oj]=false;
        }
    }
    return min!=Integer.MAX_VALUE?min:-1;
}
/**
 * 推箱子主BFS
 * @param flag 道路矩阵，false表示可通，true表示不可通
 * @param n 矩阵的行
 * @param m 矩阵的列
 * @param oi 箱子的行坐标
 * @param oj 箱子的列坐标
 * @param ei 目的地的行坐标
 * @param ej 目的地的列坐标
 * @param index 人相对箱子的位置
 * @return 最短路径值
 */
private static int bfs1(boolean[][] flag,int n,int m, int oi, int oj,int ei,int ej,int index) {
    Queue<String> queuePoint=new LinkedList<>();//箱子坐标
    Queue<Integer> queueNum=new LinkedList<>();//总共走的步数
    Queue<Integer> queueIndex=new LinkedList<>();//对应箱子坐标的人的坐标：1表示上边，2表示右面，3表示下边，4表示左面
    int min=Integer.MAX_VALUE;
    int temp,num;
    String st;
    num=0;
    //由上面的可以知道不可能O和E重合oi==ei&&oj==ej
    while (true){
        //上
        if(oi-1>=0){
            //满足可达，且不为边界
            if(!flag[oi-1][oj]){
                if(oi+1<n&&!flag[oi+1][oj]){
                    flag[oi][oj]=true;
                    //计算前一个点到后一个点的最短路劲
                    switch (index){
                        case 1:temp=bfs(flag,n,m,oi-1,oj,oi+1,oj);break;
                        case 2:temp=bfs(flag,n,m,oi,oj+1,oi+1,oj);break;
                        case 3:temp=0;break;
                        default:temp=bfs(flag,n,m,oi,oj-1,oi+1,oj);
                    }
                    if(temp!=-1){
                        //num+=temp+1;//前一个点到达箱子移动方向后面点得步数+1
                        queuePoint.offer(String.valueOf(oi-1)+"#"+String.valueOf(oj));
                        queueIndex.offer(3);
                        queueNum.offer(num+temp+1);
                    }
                    flag[oi][oj]=false;
                }
            }
        }
        //右
        if(oj+1<m){
            if(!flag[oi][oj+1]){
                if(oj-1>=0&&!flag[oi][oj-1]){
                    flag[oi][oj]=true;
                    switch (index){
                        case 1:temp=bfs(flag,n,m,oi-1,oj,oi,oj-1);break;
                        case 2:temp=bfs(flag,n,m,oi,oj+1,oi,oj-1);break;
                        case 3:temp=bfs(flag,n,m,oi+1,oj,oi,oj-1);break;
                        default:temp=0;
                    }
                    if(temp!=-1){
                        queuePoint.offer(String.valueOf(oi)+"#"+String.valueOf(oj+1));
                        queueIndex.offer(4);
                        queueNum.offer(num+temp+1);
                    }
                    flag[oi][oj]=false;
                }
            }
        }
        //下
        if(oi+1<n){
            if(!flag[oi+1][oj]){
                if(oi-1>=0&&!flag[oi-1][oj]){
                    flag[oi][oj]=true;
                    switch (index){
                        case 1:temp=0;break;
                        case 2:temp=bfs(flag,n,m,oi,oj+1,oi-1,oj);break;
                        case 3:temp=bfs(flag,n,m,oi+1,oj,oi-1,oj);break;
                        default:temp=bfs(flag,n,m,oi,oj-1,oi-1,oj);break;
                    }
                    if(temp!=-1){
                        queuePoint.offer(String.valueOf(oi+1)+"#"+String.valueOf(oj));
                        queueIndex.offer(1);
                        queueNum.offer(num+temp+1);
                    }
                    flag[oi][oj]=false;
                }
            }
        }
        //左
        if(oj-1>=0){
            if(!flag[oi][oj-1]){
                if(oj+1<m&&!flag[oi][oj+1]){
                    flag[oi][oj]=true;
                    switch (index){
                        case 1:temp=bfs(flag,n,m,oi-1,oj,oi,oj+1);break;
                        case 2:temp=0;break;
                        case 3:temp=bfs(flag,n,m,oi+1,oj,oi,oj+1);break;
                        default:temp=bfs(flag,n,m,oi,oj-1,oi,oj+1);break;
                    }
                    if(temp!=-1){
                        queuePoint.offer(String.valueOf(oi)+"#"+String.valueOf(oj-1));
                        queueIndex.offer(2);
                        queueNum.offer(num+temp+1);
                    }
                    flag[oi][oj]=false;
                }
            }
        }
        //取点
        if(!queuePoint.isEmpty()){
            while (!queueNum.isEmpty()&&queueNum.peek()>min){
                queuePoint.poll();
                queueIndex.poll();
                queueNum.poll();
            }
            if(queueNum.isEmpty())return min!=Integer.MAX_VALUE?min:-1;
            st=queuePoint.poll();
            oi=Integer.parseInt(st.split("#")[0]);
            oj=Integer.parseInt(st.split("#")[1]);
            num=queueNum.poll();
            index=queueIndex.poll();
            if(oi==ei&&oj==ej){
                if(min>num)min=num;
                while (!queueNum.isEmpty()&&queueNum.peek()>min){
                    queuePoint.poll();
                    queueIndex.poll();
                    queueNum.poll();
                }
                if(queueNum.isEmpty())return min!=Integer.MAX_VALUE?min:-1;
                st=queuePoint.poll();
                oi=Integer.parseInt(st.split("#")[0]);
                oj=Integer.parseInt(st.split("#")[1]);
                num=queueNum.poll();
                index=queueIndex.poll();
            }
        }else return min!=Integer.MAX_VALUE?min:-1;
    }
}
/**
 * 推箱子从BFS
 * @param preflag 道路矩阵，false表示可通，true表示不可通
 * @param n 矩阵行
 * @param m 矩阵列
 * @param si 起点行坐标
 * @param sj 起点列坐标
 * @param ei 终点行坐标
 * @param ej 终点列坐标
 * @return 最短路径长度
 */
private static int bfs(boolean[][] preflag, int n,int m, int si, int sj,int ei,int ej) {
    if(!((si>=0&&si<n)&&(ei>=0&&ei<n)&&(sj>=0&&sj<m)&&(ej>=0&&ej<m)))return -1;//越界返回-1
    Queue<String> queue=new LinkedList<>();
    int num=0;//步数
    String temp;
    boolean insert=true;//第一次插入#，下面每走一步插入一个#，这样就可以知道走得步数
    //必须满足si，sj是终点直接返回0
    if(si==ei&&sj==ej)return num;
    //禁止修改原道路矩阵
    boolean[][]flag=new boolean[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            flag[i][j]=preflag[i][j];
        }
    }
    while (true){
        //上
        if(si-1>=0){
            if(si-1==ei&&sj==ej) return num+1;
            else if(!flag[si-1][sj]) {
                queue.offer(String.valueOf(si-1)+"#"+String.valueOf(sj));
                flag[si-1][sj]=true;
            }
        }
        //右
        if(sj+1<m){
            if(si==ei&&sj+1==ej)return num+1;
            else if(!flag[si][sj+1]){
                queue.offer(String.valueOf(si)+"#"+String.valueOf(sj+1));
                flag[si][sj+1]=true;
            }
        }
        //下
        if(si+1<n){
            if(si+1==ei&&sj==ej)return num+1;
            else if(!flag[si+1][sj]){
                queue.offer(String.valueOf(si+1)+"#"+String.valueOf(sj));
                flag[si+1][sj]=true;
            }
        }
        //左
        if(sj-1>=0){
            if(si==ei&&sj-1==ej)return num+1;
            else if(!flag[si][sj-1]){
                queue.offer(String.valueOf(si)+"#"+String.valueOf(sj-1));
                flag[si][sj-1]=true;
            }
        }
        if(!queue.isEmpty()){
            if(insert==true){
                num++;
                queue.offer("#");
                insert=false;
            }
            temp=queue.poll();
            if(temp.equals("#")){
                num++;
                if(!queue.isEmpty()){
                    temp=queue.poll();
                    queue.offer("#");
                }else return -1;
            }
            si=Integer.parseInt(temp.split("#")[0]);
            sj=Integer.parseInt(temp.split("#")[1]);
        }else return -1;
    }
}
如果觉得有帮助，给我打赏吧！