Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.46 KB | None | 0 0
  1. import java.io.File;
  2. import java.io.FileNotFoundException;
  3. import java.util.Scanner;
  4.  
  5. public class MaxTurtlePath {
  6.  
  7.     public static void main(String[] args) throws FileNotFoundException {
  8.        
  9.         Scanner sc = new Scanner(System.in);
  10.         int N = sc.nextInt();
  11.         int M = sc.nextInt();
  12.        
  13.         int[][] arr = new int[N][M];
  14.         int[][] G = new int[N][M];
  15.         int[][] P = new int[N][M];
  16.        
  17.        
  18.         for (int i = 0; i < N; i++) {
  19.             for (int j = 0; j < M; j++) {
  20.                 arr[i][j] = sc.nextInt();
  21.             }
  22.         }
  23.        
  24.         G[0][0] = arr[0][0];
  25.        
  26.         for (int i = 1; i < N; i++) {
  27.             G[i][0] = G[i - 1][0] + arr[i][0];
  28.         }
  29.        
  30.         for (int j = 1; j < M; j++) {
  31.             G[0][j] = G[0][j - 1] + arr[0][j];
  32.         }
  33.        
  34.         for (int i = 1; i < N; i++) {
  35.             for (int j = 1; j < M; j++) {
  36.                 if(G[i - 1][j] > G[i][j - 1]) {
  37.                     P[i][j] = 1;
  38.                 } else {
  39.                     P[i][j] = 0;
  40.                 }
  41.                 G[i][j] = Math.max(G[i - 1][j], G[i][j - 1]) + arr[i][j];
  42.             }
  43.         }
  44.        
  45.         int[] A = new int[N + M - 1];
  46.        
  47.         int K = 0;
  48.         int X = N - 1;
  49.         int Y = M - 1;
  50.         while (X > 0 || Y > 0) {
  51.             A[K] = P[X][Y];
  52.             if(P[X][Y] == 0) {
  53.                 Y = Y - 1;
  54.             } else {
  55.                 X = X - 1;
  56.             }
  57.             K++;
  58.         }
  59.         if(Y > 0) {
  60.             for(int i = 0; i < Y; i++) {
  61.                 A[K] = P[0][Y - i];
  62.                 K++;
  63.             }
  64.         }
  65.         if(X > 0) {
  66.             for(int i = 0; i < X; i++) {
  67.                 A[K] = P[X - i][0];
  68.                 K++;
  69.             }
  70.         }
  71.         for(int i = K - 1; i >= 0; i--) {
  72.             if(A[i] == 1) {
  73.                 System.out.print("D ");
  74.             } else {
  75.                 System.out.print("R ");
  76.             }
  77.         }
  78.     }
  79.  
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement