怎样自己搭建一个做影视的网站,特效网站大全,简述新建站点的步骤,包头网站建设推广目录 1.题目2.思路3.代码实现#xff08;Java#xff09; 1.题目
给你一个 m x n 的迷宫矩阵 maze #xff08;下标从 0 开始#xff09;#xff0c;矩阵中有空格子#xff08;用 ‘.’ 表示#xff09;和墙#xff08;用 ‘’ 表示#xff09;。同时给你迷宫的入口 … 目录 1.题目2.思路3.代码实现Java 1.题目
给你一个 m x n 的迷宫矩阵 maze 下标从 0 开始矩阵中有空格子用 ‘.’ 表示和墙用 ‘’ 表示。同时给你迷宫的入口 entrance 用 entrance [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作你可以往 上下左 或者右移动一个格子。你不能进入墙所在的格子你也不能离开迷宫。你的目标是找到离 entrance 最近的出口。出口的含义是 maze 边界上的空格子。entrance 格子不算出口。
请你返回从 entrance 到最近出口的最短路径的步数 如果不存在这样的路径请你返回 -1。
示例 1 输入maze [[“”,“”,“.”,“”],[“.”,“.”,“.”,“”],[“”,“”,“”,“.”]], entrance [1,2] 输出1 解释总共有 3 个出口分别位于 (1,0)(0,2) 和 (2,3) 。 一开始你在入口格子 (1,2) 处。
你可以往左移动 2 步到达 (1,0) 。你可以往上移动 1 步到达 (0,2) 。 从入口处没法到达 (2,3) 。 所以最近的出口是 (0,2) 距离为 1 步。
示例 2 输入maze [[“”,“”,“”],[“.”,“.”,“.”],[“”,“”,“”]], entrance [1,0] 输出2 解释迷宫中只有 1 个出口在 (1,2) 处。 (1,0) 不算出口因为它是入口格子。 初始时你在入口与格子 (1,0) 处。
你可以往右移动 2 步到达 (1,2) 处。 所以最近的出口为 (1,2) 距离为 2 步。
示例 3
输入maze [[“.”,“”]], entrance [0,0] 输出-1 解释这个迷宫中没有出口。
提示 maze.length m maze[i].length n 1 m, n 100 maze[i][j] 要么是 ‘.’ 要么是 ‘’ 。 entrance.length 2 0 entrancerow m 0 entrancecol n entrance 一定是空格子。
2.思路
1BFS
3.代码实现Java
//思路1————BFS
class Solution {public int nearestExit(char[][] maze, int[] entrance) {int m maze.length;int n maze[0].length;int[][] dirs {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};Queueint[] queue new LinkedList();queue.offer(new int[]{entrance[0], entrance[1], 0});maze[entrance[0]][entrance[1]] ;while (!queue.isEmpty()) {int[] curPos queue.poll();int curX curPos[0];int curY curPos[1];int dis curPos[2];//朝上下左右四个方向进行遍历for (int[] dir : dirs) {int nx curX dir[0];int ny curY dir[1];if (nx 0 nx m ny 0 ny n maze[nx][ny] .) {if (nx 0 || nx m - 1 || ny 0 || ny n - 1) {return dis 1;}maze[nx][ny] ;queue.offer(new int[]{nx, ny, dis 1});}}}return -1;}
}
