Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.File;
- import java.io.FileNotFoundException;
- import java.util.Scanner;
- public class MaxTurtlePath {
- public static void main(String[] args) throws FileNotFoundException {
- Scanner sc = new Scanner(System.in);
- int N = sc.nextInt();
- int M = sc.nextInt();
- int[][] arr = new int[N][M];
- int[][] G = new int[N][M];
- int[][] P = new int[N][M];
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < M; j++) {
- arr[i][j] = sc.nextInt();
- }
- }
- G[0][0] = arr[0][0];
- for (int i = 1; i < N; i++) {
- G[i][0] = G[i - 1][0] + arr[i][0];
- }
- for (int j = 1; j < M; j++) {
- G[0][j] = G[0][j - 1] + arr[0][j];
- }
- for (int i = 1; i < N; i++) {
- for (int j = 1; j < M; j++) {
- if(G[i - 1][j] > G[i][j - 1]) {
- P[i][j] = 1;
- } else {
- P[i][j] = 0;
- }
- G[i][j] = Math.max(G[i - 1][j], G[i][j - 1]) + arr[i][j];
- }
- }
- int[] A = new int[N + M - 1];
- int K = 0;
- int X = N - 1;
- int Y = M - 1;
- while (X > 0 || Y > 0) {
- A[K] = P[X][Y];
- if(P[X][Y] == 0) {
- Y = Y - 1;
- } else {
- X = X - 1;
- }
- K++;
- }
- if(Y > 0) {
- for(int i = 0; i < Y; i++) {
- A[K] = P[0][Y - i];
- K++;
- }
- }
- if(X > 0) {
- for(int i = 0; i < X; i++) {
- A[K] = P[X - i][0];
- K++;
- }
- }
- for(int i = K - 1; i >= 0; i--) {
- if(A[i] == 1) {
- System.out.print("D ");
- } else {
- System.out.print("R ");
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement