[백준] 4485번 녹색 옷 입은 애가 젤다지? (gold 4

import java.io.*;
import java.util.*;

class Point{
    int x;
    int y;
    int v;
    public Point(int x, int y, int v){
        this.x=x;
        this.y=y;
        this.v=v;
    }
}
public class Main{
    static int[] numx={-1,1,0,0};
    static int[] numy={0,0,-1,1};
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int t=0;
        while(true){
            int n=Integer.valueOf(br.readLine());
            if(n==0){
                break;
            }
            t++;

            int[][] map=new int[n+1][n+1];
            for(int i=1; i<=n; i++){
                st=new StringTokenizer(br.readLine());
                for(int j=1; j<=n; j++){
                    map[i][j]=Integer.valueOf(st.nextToken());
                }
            }

            PriorityQueue<Point> que=new PriorityQueue<>(new Comparator<Point>(){
                public int compare(Point o1, Point o2){
                    return o1.v-o2.v;
                }
            });

            boolean[][] visit=new boolean[n+1][n+1];

            que.offer(new Point(1,1,map[1][1]));
            visit[1][1]=true;
            while(!que.isEmpty()){
                Point temp=que.poll();
                if(temp.y==n && temp.x==n){
                    bw.write("Problem "+t+": "+temp.v+"\n");
                    break;
                }

                for(int i=0; i<4; i++){
                    int tx=temp.x+numx[i];
                    int ty=temp.y+numy[i];

                    if(tx<1 || tx>n || ty<1 || ty>n || visit[ty][tx]){
                        continue;
                    }
                    visit[ty][tx]=true;
                    que.offer(new Point(tx, ty , temp.v+map[ty][tx]));
                }
            }
        }
        bw.flush();
    }
}

//pq로 순서만 잘 정해주면 해결되는 간단한 bfs문제ㅁ