SW Expert 보급로 (자바)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class algo_1249_김어진 {
	public static int[] dx = { -1,0,1,0};
	public static int[] dy = {0,1,0,-1};
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int test_case = Integer.parseInt(st.nextToken());
		for (int tc = 1; tc <= test_case; tc++) {
			int answer = 0;
			st = new StringTokenizer(br.readLine()," ");
			int N = Integer.parseInt(st.nextToken());
			int[][] board= new int[N][N];
			boolean[][] check = new boolean[N][N];
			for (int i = 0; i < N; i++) {
				char[] chr = br.readLine().toCharArray();
				for (int j = 0; j < N; j++) {
					board[i][j] = chr[j]-'0';
				}
			}
			
			PriorityQueue<Node> q= new PriorityQueue<>((a,b)->a.cost - b.cost);
			
			q.add(new Node(0,0,0));
			while(!q.isEmpty())
			{
				Node now = q.poll();
				int x = now.x;
				int y = now.y;
				int cost =now.cost;
				if(x==N-1 && y==N-1) {
					answer = cost;
					break;
				}
				for (int i = 0; i < 4; i++) {
					int nx = x+dx[i];
					int ny = y +dy[i];
					if(nx>=0 && nx < N && ny>=0 && ny<N && !check[nx][ny] ) {
						q.add(new Node(nx,ny,cost+board[nx][ny]));
						check[nx][ny]=true;
					}
				}
			}
			
			
			System.out.printf("#%d %d\n",tc,answer);
		}
				
	}
	static class Node{
		
		int x;
		int y;
		int cost;
		
		public Node(int x, int y, int cost) {
			super();
			this.x = x;
			this.y = y;
			this.cost = cost;
		}
	}
}