daily pastebin goal
25%
SHARE
TWEET

Untitled

a guest Dec 9th, 2018 51 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.InputStreamReader;
  5. import java.util.PriorityQueue;
  6. import java.util.StringTokenizer;
  7.  
  8. public class MAGRID {
  9.     static int[][] a = new int[510][510];
  10.     static boolean[][] v = new boolean[510][510];
  11.     static int R, C;
  12.  
  13.     public static void main(String[] args) throws Exception {
  14.         InputReader in = new InputReader(System.in);
  15.         int t = in.nextInt();
  16.         while (t-- > 0) {
  17.             R = in.nextInt();
  18.             C = in.nextInt();
  19.             for (int i = 0; i < R; i++)
  20.                 for (int j = 0; j < C; j++)
  21.                     a[i][j] = in.nextInt();
  22.             long lo = 1;
  23.             long hi = 250000010;
  24.             long mid;
  25.             long cst;
  26.             int i, j;
  27.             long ans;
  28.             while (lo < hi) {
  29.                 PriorityQueue<state> pq = new PriorityQueue<state>();
  30.                 for (i = 0; i < R; i++)
  31.                     for (j = 0; j < C; j++)
  32.                         v[i][j] = false;
  33.                 mid = (lo + hi) / 2;
  34.                 pq.add(new state(0, 0, mid));
  35.                 state cur;
  36.                 ans = -1;
  37.                 while (!pq.isEmpty()) {
  38.                     cur = pq.poll();
  39.                     cst = cur.cst;
  40.                     i = cur.i;
  41.                     j = cur.j;
  42.                     if (i == R - 1 && j == C - 1) {
  43.                         ans = cst;
  44.                         break;
  45.                     }
  46.                     v[i][j] = true;
  47.                     if (i + 1 < R && !v[i + 1][j] && cst + a[i + 1][j] > 0)
  48.                         pq.add(new state(i + 1, j, cst + a[i + 1][j]));
  49.                     if (j + 1 < C && !v[i][j + 1] && cst + a[i][j + 1] > 0)
  50.                         pq.add(new state(i, j + 1, cst + a[i][j + 1]));
  51.                 }
  52.                 if (ans <= 0) {
  53.                     lo = mid + 1;
  54.                 } else {
  55.                     hi = mid;
  56.                 }
  57.             }
  58.             System.out.println(lo);
  59.         }
  60.     }
  61.  
  62.     static class state implements Comparable<state> {
  63.         int i, j;
  64.         long cst;
  65.  
  66.         public state(int ii, int jj, long cost) {
  67.             cst = cost;
  68.             i = ii;
  69.             j = jj;
  70.         }
  71.  
  72.         @Override
  73.         public int compareTo(state o) {
  74.             if (o.cst < cst)
  75.                 return -1;
  76.             if (o.cst > cst)
  77.                 return 1;
  78.             return 0;
  79.         }
  80.  
  81.     }
  82.  
  83.     // private static long solve(int i, int j) {
  84.     // if(i>=R||i<0||j>=C||j<0)return 0;
  85.     // if(i==R-1&&j==C-1)return a[i][j];
  86.     // if(dp[i][j]!=-1)
  87.     // return dp[i][j];
  88.     // long max = Integer.MIN_VALUE;
  89.     // max = Math.max(max, solve(i+1,j)+a[i][j]);
  90.     // max = Math.max(max, solve(i,j+1)+a[i][j]);
  91.     // return dp[i][j]=max;
  92.     // }
  93.  
  94.     static class InputReader {
  95.         private BufferedReader reader;
  96.         private StringTokenizer tokenizer;
  97.  
  98.         public InputReader(InputStream stream) {
  99.             reader = new BufferedReader(new InputStreamReader(stream));
  100.             tokenizer = null;
  101.         }
  102.  
  103.         public String next() {
  104.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  105.                 try {
  106.                     tokenizer = new StringTokenizer(reader.readLine());
  107.                 } catch (IOException e) {
  108.                     throw new RuntimeException(e);
  109.                 }
  110.             }
  111.             return tokenizer.nextToken();
  112.         }
  113.  
  114.         public int nextInt() {
  115.             return Integer.parseInt(next());
  116.         }
  117.     }
  118. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top