HackerEarth Capture Castle problem solution

In this HackerEarth Capture Castle problem solution HackerMan loves playing Age of Empire. A few days ago, he discovered a variant of that game which is equally adventurous. Here, he has to capture a castle before his enemy.

The map consists of several interconnected paths in a grid pattern. He starts at top left intersection (1,1), and then proceeds towards the castle. But every intersection has some dark magical power which stops him from escaping that intersection for some time. Also, the enemy is moving towards the castle. So he has to reach the castle before his enemy. Given the time t at which the enemy captures the castle, you have to determine if it is possible for HackerMan to capture the castle himself.

The first line contains the number of test cases T (1 <= T <= 100). In each test case, the first line contains two integers M and N indicating the number of rows and columns in the grid of paths. Then follows M lines, each line contains N positive integers. The integer at (i,j) in the grid denotes the time taken to escape that intersection. Then follows another line which contains 3 positive integers - x, y, and t, where (x,y) is the position of castle and t is time at which enemy captures the castle.

You have to print NO if it is not possible to capture the castle before time t. If it is possible, print YES followed by a newline and then print the time left before which the enemy reaches the castle. You need to prepare for the war then :)

HackerEarth Capture Castle problem solution.

import java.io.*;
import java.util.*;
public final class capture_castle
{
    static Scanner sc=new Scanner(System.in);
    static PrintWriter out=new PrintWriter(System.out);
    static long[][] dis;
    static final String s1="YES",s2="NO";

    public static void main(String args[]) throws Exception
    {
        int t=sc.nextInt();
        while(t>0)
        {
            int n=sc.nextInt(),m=sc.nextInt();
            long[][] a=new long[n][m],dis=new long[n][m];
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    a[i][j]=sc.nextLong();
                    dis[i][j]=Long.MAX_VALUE;
                }
            }
            int x=sc.nextInt()-1,y=sc.nextInt()-1;
            long min2=sc.nextLong();
            PriorityQueue<Node> pq=new PriorityQueue<Node>();
            pq.add(new Node(0,0,a[0][0]));
            dis[0][0]=a[0][0];
            while(pq.size()>0)
            {
                Node curr=pq.poll();
                int i=curr.i,j=curr.j;
                if(i-1>=0 && dis[i-1][j]>dis[i][j]+a[i-1][j])
                {
                    dis[i-1][j]=dis[i][j]+a[i-1][j];
                    pq.add(new Node(i-1,j,dis[i-1][j]));
                }
                if(i+1<n && dis[i+1][j]>dis[i][j]+a[i+1][j])
                {
                    dis[i+1][j]=dis[i][j]+a[i+1][j];
                    pq.add(new Node(i+1,j,dis[i+1][j]));
                }
                if(j-1>=0 && dis[i][j-1]>dis[i][j]+a[i][j-1])
                {
                    dis[i][j-1]=dis[i][j]+a[i][j-1];
                    pq.add(new Node(i,j-1,dis[i][j-1]));
                }
                if(j+1<m && dis[i][j+1]>dis[i][j]+a[i][j+1])
                {
                    dis[i][j+1]=dis[i][j]+a[i][j+1];
                    pq.add(new Node(i,j+1,dis[i][j+1]));
                }
            }
            long ans=min2-dis[x][y];
            if(ans>0)
            {
                out.println(s1+"\n"+ans);
            }
            else
            {
                out.println(s2);
            }
            t--;
        }
        out.close();
    }
}
class Node implements Comparable<Node>
{
    int i,j;
    long cost;
    public Node(int i,int j,long cost)
    {
        this.i=i;
        this.j=j;
        this.cost=cost;
    }
    public int compareTo(Node x)
    {
        return Long.compare(this.cost,x.cost);
    }
}