品牌型网站建设方案,个人网页制作成品 模板,app开发合同模板最新版,seo第三方点击软件4943. 方格迷宫 - AcWing题库 1、题目
给定一个 n 行 m 列的方格矩阵。
行从上到下依次编号为 1∼n#xff0c;列从左到右依次编号为 1∼m。
第 i 行第 j 列的方格表示为 (i,j)。
矩阵中的方格要么是空地#xff08;用 . 表示#xff09;#xff0c;要么是陷阱#xf…4943. 方格迷宫 - AcWing题库 1、题目
给定一个 n 行 m 列的方格矩阵。
行从上到下依次编号为 1∼n列从左到右依次编号为 1∼m。
第 i 行第 j 列的方格表示为 (i,j)。
矩阵中的方格要么是空地用 . 表示要么是陷阱用 # 表示。
初始时你位于方格 (x₁,y₁)你需要前往方格 (x₂,y₂)。
每次移动你可以任选上、下、左、右四个方向之一并沿该方向移动 1∼k 步。
从一个方格移动至相邻方格视为一步。
但是你要保证在你的移动过程中不能走出矩阵也不能进入陷阱方格。
请你计算从方格 (x₁,y₁) 移动至方格 (x₂,y₂)所需要的最少移动次数。
保证方格 (x₁,y₁) 和方格 (x₂,y₂) 都是空地。
方格 (x₁,y₁) 和方格 (x₂,y₂) 可能是同一个方格。
注意注意区分本题中移动次数与移动步数的区别。
输入格式
第一行包含三个整数 n,m,k。
接下来 n 行每行包含 m 个字符其中第 i 行第 j 个字符要么是 .表示方格 (i,j) 是空地要么是 #表示方格 (i,j) 是陷阱。
最后一行包含四个整数 x₁,y₁,x₂,y₂。
输出格式
一个整数表示所需要的最少移动次数。
如果无法从方格 (x₁,y₁) 移动至方格 (x₂,y₂)则输出 -1。
数据范围
前 6 个测试点满足 1≤n,m≤10。 所有测试点满足 1≤n,m,k≤10001≤x₁,x₂≤n1≤y₂,y₂≤m。
输入样例1
3 4 4
....
###.
....
1 1 3 1输出样例1
3输入样例2
3 4 1
....
###.
....
1 1 3 1
输出样例2
8输入样例3
2 2 1
.#
#.
1 1 2 2输出样例3
-1
2、题目解读 走迷宫_牛客题霸_牛客网 (nowcoder.com) 牛客网这题就是正常普通求解最短步数的迷宫问题而这题添加了一个条件每次移动你可以任选上、下、左、右四个方向之一并沿该方向移动 1∼k 步。这称为 一次移动。 我们使用BFS去正常解答这道题目时间复杂度为Onmk最大为10⁹这就会超时。 import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static int n,m,k,x1,x2,y1,y2;static char[][] ch;static int[][] move {{0,1},{0,-1},{1,0},{-1,0}};//四个方向偏移量static int inf0x3f3f3f3f;//初始化移动次数static int[][] ans;//记录移动次数public static void main(String[] args){Scanner scnew Scanner(System.in);nsc.nextInt();msc.nextInt();ksc.nextInt();ch new char[n][];ans new int[n][m];for(int i0;in;i){ch[i]sc.next().toCharArray();}x1sc.nextInt()-1;y1sc.nextInt()-1;x2sc.nextInt()-1;y2sc.nextInt()-1;for(int i0;in;i){//初始化移动次数Arrays.fill(ans[i],inf);}System.out.println(bfs());}public static int bfs(){ans[x1][y1]0;Queueint[] qnew LinkedList();q.add(new int[]{x1,y1,0});while(!q.isEmpty()){int[] a q.poll();for(int[] mo :move){//四个方向for(int i1;ik;i){//移动一次移动1-k步int xa[0]mo[0]*i,ya[1]mo[1]*i;if(x0||xn||y0||ym||ch[x][y]#){//不能出去不能跨越陷阱break;}if(ans[x][y]a[2]1){//修改移动次数ans[x][y]a[2]1;q.add(new int[]{x,y,a[2]1});}}}}//走完整个地图判断目的地是否可以走到return ans[x2][y2]inf?-1:ans[x2][y2];}
}我们需要优化代码看下面图 所以我们应该 更新到格子发现不是最优就应该停止。这样时间复杂度就退化到了Onm 需要在判断条件处新加ans[x][y]a[2]1 3、代码 import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static int n,m,k,x1,x2,y1,y2;static char[][] ch;static int[][] move {{0,1},{0,-1},{1,0},{-1,0}};//四个方向偏移量static int inf0x3f3f3f3f;//初始化移动次数static int[][] ans;//记录移动次数public static void main(String[] args){Scanner scnew Scanner(System.in);nsc.nextInt();msc.nextInt();ksc.nextInt();ch new char[n][];ans new int[n][m];for(int i0;in;i){ch[i]sc.next().toCharArray();}x1sc.nextInt()-1;y1sc.nextInt()-1;x2sc.nextInt()-1;y2sc.nextInt()-1;for(int i0;in;i){//初始化移动次数Arrays.fill(ans[i],inf);}System.out.println(bfs());}public static int bfs(){ans[x1][y1]0;Queueint[] qnew LinkedList();q.add(new int[]{x1,y1,0});while(!q.isEmpty()){int[] a q.poll();for(int[] mo :move){//四个方向for(int i1;ik;i){//移动一次移动1-k步int xa[0]mo[0]*i,ya[1]mo[1]*i;//不能出去不能跨越陷阱还有更新到格子发现不是最优就应该停止if(x0||xn||y0||ym||ch[x][y]#||ans[x][y]a[2]1){break;}if(ans[x][y]a[2]1){//修改移动次数ans[x][y]a[2]1;q.add(new int[]{x,y,a[2]1});}}}}//走完整个地图判断目的地是否可以走到return ans[x2][y2]inf?-1:ans[x2][y2];}
}
