DeepSeek LeetCode 1210. 穿过迷宫的最少移动次数 public int minimumMoves(int[][] grid)

我来分析 LeetCode 1210 “穿过迷宫的最少移动次数” 的解题思路和实现。问题分析我们有一条长度为 2 的蛇需要从起点(0,0)和(0,1)水平放置移动到终点(n-1, n-2)和(n-1, n-1)仍为水平放置。蛇可以向右移动向下移动顺时针旋转当蛇水平放置时向下旋转逆时针旋转当蛇垂直放置时向右旋转解题思路方法一BFS 状态搜索将蛇的状态表示为(tailX, tailY, direction)其中direction 0表示水平放置蛇尾在左蛇头在右direction 1表示垂直放置蛇尾在上蛇头在下publicintminimumMoves(int[][]grid){intngrid.length;// 状态: (tailX, tailY, direction)// direction: 0-水平, 1-垂直boolean[][][]visitednewboolean[n][n][2];Queueint[]queuenewLinkedList();// 起始状态: 蛇尾在(0,0), 水平放置queue.offer(newint[]{0,0,0});// {x, y, dir}visited[0][0][0]true;intsteps0;while(!queue.isEmpty()){intsizequeue.size();for(inti0;isize;i){int[]statequeue.poll();intxstate[0];// 蛇尾x坐标intystate[1];// 蛇尾y坐标intdirstate[2];// 方向// 检查是否到达终点if(xn-1yn-2dir0){returnsteps;}// 获取蛇头坐标intheadXx,headYy;if(dir0){headYy1;// 水平: 蛇头在右侧}else{headXx1;// 垂直: 蛇头在下方}// 1. 向右移动if(canMoveRight(grid,x,y,dir,n)){intnewXx;intnewYy1;if(!visited[newX][newY][dir]){visited[newX][newY][dir]true;queue.offer(newint[]{newX,newY,dir});}}// 2. 向下移动if(canMoveDown(grid,x,y,dir,n)){intnewXx1;intnewYy;if(!visited[newX][newY][dir]){visited[newX][newY][dir]true;queue.offer(newint[]{newX,newY,dir});}}// 3. 旋转if(dir0){// 水平 - 垂直顺时针旋转if(canRotateClockwise(grid,x,y,n)){if(!visited[x][y][1]){visited[x][y][1]true;queue.offer(newint[]{x,y,1});}}}else{// 垂直 - 水平逆时针旋转if(canRotateCounterClockwise(grid,x,y,n)){if(!visited[x][y][0]){visited[x][y][0]true;queue.offer(newint[]{x,y,0});}}}}steps;}return-1;}// 检查是否可以向右移动privatebooleancanMoveRight(int[][]grid,intx,inty,intdir,intn){if(dir0){// 水平放置: 需要检查蛇头和蛇尾右侧的格子if(y2n)returnfalse;returngrid[x][y2]0;}else{// 垂直放置: 需要检查蛇头和蛇尾右侧的格子if(y1n||x1n)returnfalse;returngrid[x][y1]0grid[x1][y1]0;}}// 检查是否可以向下移动privatebooleancanMoveDown(int[][]grid,intx,inty,intdir,intn){if(dir0){// 水平放置: 需要检查蛇头和蛇尾下方的格子if(x1n)returnfalse;returngrid[x1][y]0grid[x1][y1]0;}else{// 垂直放置: 需要检查蛇头下方和蛇尾下方的格子if(x2n)returnfalse;returngrid[x2][y]0;}}// 检查是否可以顺时针旋转水平 - 垂直privatebooleancanRotateClockwise(int[][]grid,intx,inty,intn){// 需要检查蛇头下方的两个格子if(x1n||y1n)returnfalse;returngrid[x1][y]0grid[x1][y1]0;}// 检查是否可以逆时针旋转垂直 - 水平privatebooleancanRotateCounterClockwise(int[][]grid,intx,inty,intn){// 需要检查蛇头右侧的两个格子if(x1n||y1n)returnfalse;returngrid[x][y1]0grid[x1][y1]0;}方法二优化版 BFS使用距离数组publicintminimumMoves(int[][]grid){intngrid.length;// dist[x][y][dir] 表示到达状态的最小步数int[][][]distnewint[n][n][2];// 初始化距离数组for(inti0;in;i){for(intj0;jn;j){Arrays.fill(dist[i][j],Integer.MAX_VALUE);}}Queueint[]queuenewLinkedList();dist[0][0][0]0;queue.offer(newint[]{0,0,0});while(!queue.isEmpty()){int[]statequeue.poll();intxstate[0],ystate[1],dirstate[2];intstepsdist[x][y][dir];// 计算蛇头位置intheadXx,headYy;if(dir0){headYy1;}else{headXx1;}// 尝试所有可能的移动// 向右移动if(canMoveRight(grid,x,y,dir,n)){intnxx,nyy1;if(steps1dist[nx][ny][dir]){dist[nx][ny][dir]steps1;queue.offer(newint[]{nx,ny,dir});}}// 向下移动if(canMoveDown(grid,x,y,dir,n)){intnxx1,nyy;if(steps1dist[nx][ny][dir]){dist[nx][ny][dir]steps1;queue.offer(newint[]{nx,ny,dir});}}// 旋转if(dir0canRotateClockwise(grid,x,y,n)){if(steps1dist[x][y][1]){dist[x][y][1]steps1;queue.offer(newint[]{x,y,1});}}elseif(dir1canRotateCounterClockwise(grid,x,y,n)){if(steps1dist[x][y][0]){dist[x][y][0]steps1;queue.offer(newint[]{x,y,0});}}}returndist[n-1][n-2][0]Integer.MAX_VALUE?-1:dist[n-1][n-2][0];}方法三使用方向数组简化代码publicintminimumMoves(int[][]grid){intngrid.length;boolean[][][]visitednewboolean[n][n][2];// 移动操作: {dx, dy, newDir, checkFunction}// 这里简化直接在循环中判断Queueint[]queuenewLinkedList();queue.offer(newint[]{0,0,0});visited[0][0][0]true;intsteps0;while(!queue.isEmpty()){intsizequeue.size();for(inti0;isize;i){int[]currqueue.poll();intxcurr[0],ycurr[1],dircurr[2];// 检查终点if(xn-1yn-2dir0){returnsteps;}// 获取蛇头坐标inthxdir0?x:x1;inthydir0?y1:y;// 尝试所有可能的移动// 右移if(hy1n){if(dir0grid[x][hy1]0){// 水平右移if(!visited[x][y1][0]){visited[x][y1][0]true;queue.offer(newint[]{x,y1,0});}}elseif(dir1grid[x][hy]0grid[hx][hy]0){// 垂直右移if(!visited[x][y1][1]){visited[x][y1][1]true;queue.offer(newint[]{x,y1,1});}}}// 下移if(hx1n){if(dir0grid[hx][y]0grid[hx][hy]0){// 水平下移if(!visited[x1][y][0]){visited[x1][y][0]true;queue.offer(newint[]{x1,y,0});}}elseif(dir1grid[hx1][y]0){// 垂直下移if(!visited[x1][y][1]){visited[x1][y][1]true;queue.offer(newint[]{x1,y,1});}}}// 旋转if(x1ny1n){// 检查旋转所需的两个格子if(grid[x1][y]0grid[x1][y1]0){if(dir0!visited[x][y][1]){// 水平转垂直visited[x][y][1]true;queue.offer(newint[]{x,y,1});}elseif(dir1!visited[x][y][0]){// 垂直转水平visited[x][y][0]true;queue.offer(newint[]{x,y,0});}}}}steps;}return-1;}复杂度分析时间复杂度: O(n²)每个状态最多访问一次空间复杂度: O(n²)用于存储 visited 或 dist 数组关键点总结状态表示: 使用(尾坐标, 方向)表示蛇的状态BFS 适用性: 无权图的最短路径问题BFS 保证找到最少步数边界检查: 移动和旋转时需要检查边界和障碍物旋转条件: 旋转需要检查额外的 2×2 区域