苏州网站建设点一点网站首页大图轮播

苏州网站建设点一点,网站首页大图轮播,微信自己开发小程序,微信h5页面制作免费自动泊车 2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 100分题型 华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录#xff5c;机考题库 算法考点详解 题目描述 考友回忆版:有一个停车场#xff0c;停车场入口位置[0,0]为0#xff0c;你要…自动泊车2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 100分题型华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录机考题库 算法考点详解题目描述考友回忆版:有一个停车场停车场入口位置[0,0]为0你要停的位置为[m,n],停车场位置可能是0或者1是零的位置车可以通行是1的位置不可以通行车在停车场内可以只能往四周移动(上下左右)要求找出从入口到目标车位的最短路径如果无法到达就返回-1.输入描述输入 m n,目标车位位置输入 row ,col, 停车场大小接下来输入row行每行为停车场的位置信息。输出描述输出一个整数如果能到到达目标车位输出最短路径不能到达输出-1.用例1输入1 1 3 3 0 0 0 0 0 0 0 0 0输出2题解思路BFS,模板题这道题就是经典BFS模板题借助BFS的一个特性初次访问到某个位置肯定是最小路径。在进行BFS模拟过程中如果第一次到达m n位置可直接退出同时可以利用上面那个特性进行剪枝已经访问过的位置不再入栈。BFS基本逻辑如下定义visited初始化所有位置为-1表示未访问过。定义队列初始将{0,0}放入队列。接下来使用队列模拟BFS向四周扩散每次取出队列队首元素{x,y}向四周扩散得到{newX,newY}按照下面逻辑处理:newX 0 || newY 0 || newX row || newY col: 超过边界异常情况剪枝grid[newX][newY] 1: 不可通行位置剪枝visited[newX][newY] ! -1: 以访问过位置不再次搜索剪枝。合法情况, {newX,newY}入队并更新visisted[newX][newY] visisted[x][y] 1如果在BFS中遇到{m,n}可提前退出BFS。注意:由于这道题的题目大意时小伙伴口诉回忆的可能有部分地方有差异但总体思路应该没错大家到时候可以灵活修改一下。但是总体思路肯定时没有问题的c#includeiostream #includevector #includestring #include utility #include sstream #includealgorithm #includecmath #includemap #includequeue #includeclimits using namespace std; int bfs(vectorvectorint grid, int m, int n, int row, int col) { // 上下左右 int direct[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 异常情况细节处理 if (m 0 || n 0 || m row || n col || grid[0][0] 1) { return -1; } if (m 0 n 0) { return 0; } // 记录起点到{i,j}的 最短路径 vectorvectorint visited(row, vectorint(col, -1)); queuepairint,int q; q.push({0, 0}); visited[0][0] 0; while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); for (int i 0; i 4; i) { int newX x direct[i][0]; int newY y direct[i][1]; // 合法性检验 if (newX 0 || newY 0 || newX row || newY col) { continue; } // 不可通行 if (grid[newX][newY] 1) { continue; } // bfs特性首次到达的路径长度肯定最小 if (visited[newX][newY] ! -1) { continue; } // 入队 q.push({newX, newY}); visited[newX][newY] visited[x][y] 1; if (newX m newY n) { return visited[newX][newY]; } } } return visited[m][n] -1 ? -1 : visited[m][n]; } int main() { int m,n; cin m n; int row, col; cin row col; vectorvectorint grid(row, vectorint(col)); for (int i 0; i row; i) { for (int j 0; j col; j) { cin grid[i][j]; } } int res bfs(grid, m, n, row, col); cout res; return 0; }JAVAimport java.io.*; import java.util.*; /** * BFS 求从 (0,0) 到 (m,n) 的最短路径 * 0 表示可通行1 表示障碍 */ public class Main { static int bfs(int[][] grid, int m, int n, int row, int col) { // 上下左右方向 int[][] direct {{-1,0},{1,0},{0,-1},{0,1}}; // 异常情况处理 if (m 0 || n 0 || m row || n col || grid[0][0] 1) { return -1; } if (m 0 n 0) { return 0; } // 记录最短路径长度-1 表示未访问 int[][] visited new int[row][col]; for (int i 0; i row; i) { Arrays.fill(visited[i], -1); } Queueint[] queue new LinkedList(); queue.offer(new int[]{0, 0}); visited[0][0] 0; while (!queue.isEmpty()) { int[] cur queue.poll(); int x cur[0], y cur[1]; for (int i 0; i 4; i) { int newX x direct[i][0]; int newY y direct[i][1]; // 边界检查 if (newX 0 || newY 0 || newX row || newY col) continue; // 障碍 if (grid[newX][newY] 1) continue; // 已访问 if (visited[newX][newY] ! -1) continue; visited[newX][newY] visited[x][y] 1; if (newX m newY n) { return visited[newX][newY]; } queue.offer(new int[]{newX, newY}); } } return visited[m][n] -1 ? -1 : visited[m][n]; } public static void main(String[] args) throws Exception { Scanner sc new Scanner(System.in); int m sc.nextInt(); int n sc.nextInt(); int row sc.nextInt(); int col sc.nextInt(); int[][] grid new int[row][col]; for (int i 0; i row; i) { for (int j 0; j col; j) { grid[i][j] sc.nextInt(); } } int res bfs(grid, m, n, row, col); System.out.print(res); } }Pythonimportsysfromcollectionsimportdequedefbfs(grid,m,n,row,col):# 上下左右direct[(-1,0),(1,0),(0,-1),(0,1)]# 异常情况处理ifm0orn0ormroworncolorgrid[0][0]1:return-1ifm0andn0:return0# visited 记录最短距离-1 表示未访问visited[[-1]*colfor_inrange(row)]qdeque()q.append((0,0))visited[0][0]0whileq:x,yq.popleft()fordx,dyindirect:nx,nyxdx,ydyifnx0orny0ornxrowornycol:continueifgrid[nx][ny]1:continueifvisited[nx][ny]!-1:continuevisited[nx][ny]visited[x][y]1ifnxmandnyn:returnvisited[nx][ny]q.append((nx,ny))return-1ifvisited[m][n]-1elsevisited[m][n]defmain():datalist(map(int,sys.stdin.read().split()))idx0m,ndata[idx],data[idx1]idx2row,coldata[idx],data[idx1]idx2grid[]for_inrange(row):grid.append(data[idx:idxcol])idxcolprint(bfs(grid,m,n,row,col))if__name____main__:main()JavaScript/** * 使用 readline 接收 ACM 输入 * BFS 求从 (0,0) 到 (m,n) 的最短路径 * 0 表示可通行1 表示障碍 */use strict;constreadlinerequire(readline);// 创建 readline 接口constrlreadline.createInterface({input:process.stdin,output:process.stdout});constlines[];rl.on(line,line{lines.push(line.trim());});rl.on(close,(){// 将所有输入按空白切分为数字constdatalines.join( ).split(/\s/).map(Number);letidx0;// 目标坐标 (m, n)constmdata[idx];constndata[idx];// 网格行列constrowdata[idx];constcoldata[idx];// 读取网格constgrid[];for(leti0;irow;i){grid.push(data.slice(idx,idxcol));idxcol;}console.log(bfs(grid,m,n,row,col).toString());});/** * BFS 搜索最短路径 * param {number[][]} grid 网格 * param {number} m 目标行 * param {number} n 目标列 * param {number} row 行数 * param {number} col 列数 * returns {number} 最短路径长度无法到达返回 -1 */functionbfs(grid,m,n,row,col){// 上下左右四个方向constdirect[[-1,0],[1,0],[0,-1],[0,1]];// 异常情况处理if(m0||n0||mrow||ncol||grid[0][0]1){return-1;}// 起点就是终点if(m0n0){return0;}// visited 记录从起点到该点的最短距离-1 表示未访问constvisitedArray.from({length:row},()Array(col).fill(-1));// 使用数组模拟队列head 指针避免 shift O(n)constqueue[];lethead0;// 起点入队queue.push([0,0]);visited[0][0]0;// BFS 主循环while(headqueue.length){const[x,y]queue[head];for(const[dx,dy]ofdirect){constnxxdx;constnyydy;// 边界检查if(nx0||ny0||nxrow||nycol)continue;// 障碍物if(grid[nx][ny]1)continue;// 已访问if(visited[nx][ny]!-1)continue;// 更新最短距离visited[nx][ny]visited[x][y]1;// 如果到达目标点直接返回BFS 首次到达即最短if(nxmnyn){returnvisited[nx][ny];}// 入队queue.push([nx,ny]);}}// BFS 结束仍未到达returnvisited[m][n]-1?-1:visited[m][n];}Gopackagemainimport(bufiofmtos)// 节点结构体表示网格中的一个点typeNodestruct{x,yint}/** * BFS 求从 (0,0) 到 (m,n) 的最短路径 * 0 表示可通行1 表示障碍 */funcbfs(grid[][]int,m,n,row,colint)int{// 上下左右四个方向direct:[][]int{{-1,0},{1,0},{0,-1},{0,1},}// 异常情况处理ifm0||n0||mrow||ncol||grid[0][0]1{return-1}// 起点即终点ifm0n0{return0}// visited 记录从起点到该点的最短距离visited:make([][]int,row)fori:0;irow;i{visited[i]make([]int,col)forj:0;jcol;j{visited[i][j]-1}}// 使用切片模拟队列queue:make([]Node,0)queueappend(queue,Node{0,0})visited[0][0]0head:0forheadlen(queue){cur:queue[head]headfor_,d:rangedirect{nx:cur.xd[0]ny:cur.yd[1]// 边界检查ifnx0||ny0||nxrow||nycol{continue}// 障碍物ifgrid[nx][ny]1{continue}// 已访问ifvisited[nx][ny]!-1{continue}// 更新最短距离visited[nx][ny]visited[cur.x][cur.y]1// 到达目标点直接返回ifnxmnyn{returnvisited[nx][ny]}// 入队queueappend(queue,Node{nx,ny})}}// BFS 结束后判断是否可达ifvisited[m][n]-1{return-1}returnvisited[m][n]}funcmain(){in:bufio.NewReader(os.Stdin)varm,nintvarrow,colint// 读取目标坐标fmt.Fscan(in,m,n)// 读取网格大小fmt.Fscan(in,row,col)// 读取网格grid:make([][]int,row)fori:0;irow;i{grid[i]make([]int,col)forj:0;jcol;j{fmt.Fscan(in,grid[i][j])}}// 输出结果fmt.Print(bfs(grid,m,n,row,col))}