9.13度小满笔试

//迷宫最短路径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];
 }
}