题目大意:
给你一个矩阵代表一个闯关方格,英雄最开始在(0,0)处,移动一次耗费1s,闯关方格上的数字代表着倒计时,每过一秒减一,当减到0时该格子无法通过,求到右下角的最短时间
BFS搜索加剪枝即可
作者:相依相随 链接:https://www.nowcoder.com/discuss/719729?type=post&order=time&pos=&page=3&ncTraceId=&channel=-1&source_id=search_post_nctrack 来源:牛客网 package nowcoder; import java.io.BufferedInputStream; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main48 { public static void main(String[] args) { new Solve48().solve(); } } class Solve48{ int row,col; int[] dx={-1,1,0,0}; int[] dy={0,0,1,-1}; private class Node{ int x; int y; int hop; public Node(int x, int y, int hop) { this.x = x; this.y = y; this.hop = hop; } } public void solve(){ Scanner s=new Scanner(new BufferedInputStream(System.in)); row=s.nextInt(); col=s.nextInt(); int[][] grid=new int[row][col]; for (int i = 0; i <row ; i++) { for (int j = 0; j < col; j++) { grid[i][j]=s.nextInt(); } } System.out.println(getAns(grid)); } private int getAns(int[][] grid){ if (grid[0][0]<=0){ return -1; } int[][] minTime=new int[row][col]; for (int i = 0; i < row; i++) { Arrays.fill(minTime[i],Integer.MAX_VALUE); } Queue<Node> queue=new LinkedList<>(); queue.add(new Node(0,0,0)); while (!queue.isEmpty()){ Node node=queue.poll(); int x=node.x; int y=node.y; int hop=node.hop; // System.out.println(x+" "+y+" "+hop); if (minTime[x][y]<=hop||grid[x][y]<hop)continue; minTime[x][y]=hop; if (x==row-1&&y==col-1)return hop; for (int i = 0; i < dx.length; i++) { int nextX=dx[i]+x; int nextY=dy[i]+y; if (!inGrid(nextX,nextY))continue; queue.add(new Node(nextX,nextY,hop+1)); } } return -1; } private boolean inGrid(int x,int y){ return x>=0&&x<row&&y>=0&&y<col; } }