9.13度小满笔试
9.13度小满笔试第二题迷宫
自己本地跑没问题，结果只能ac0.3，菜的真实
//迷宫最短路径bfs
import java.util.*;
public class Main {
public static class node{
public int x;
public int y;
public node(int x, int y) {
this.x=x;
this.y=y;
}
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int m=in.nextInt();
in.nextLine();
int [][] a=new int[n][n];
for(int i=0;i<n;i++) {
String s=in.nextLine();
for(int j=0;j<n;j++) {
if(s.charAt(j)=='#') a[i][j]=m;
else a[i][j]=s.charAt(j)-'0';
}
}
System.out.print(bfs(a));
}
public static int bfs(int[][] a) {
int n=a.length;
int [][] dp=new int[n][n];
int[] dx= {1,0,-1,0};
int[]dy= {0,1,0,-1};
int sx=0,sy=0,gx=n-1,gy=n-1;
int nx,ny;
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
dp[i][j]=-1;
}
dp[0][0]=0;
}
Queue<node> que=new LinkedList();
node first=new node(sx,sy);
que.add(first);
while(!que.isEmpty()) {
node curNode=que.poll();
int cx=curNode.x;
int cy=curNode.y;
if(cx==gx&&cy==gy) {
return dp[gx][gy];
}
for(int i=0;i<4;i++) {
nx=cx+dx[i];
ny=cy+dy[i];
if((0<=nx&&nx<n)&&(0<=ny&&ny<n)&&(dp[nx][ny]==-1)&&(a[nx][ny]!=0)){
node nextNode=new node(nx,ny);
que.add(nextNode);
dp[nx][ny]=dp[cx][cy]+a[nx][ny];
}
}
}
return dp[gx][gy];
}
}
