Guest User

notfound

a guest
Apr 11th, 2019
24
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.10 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.Arrays;
  6. import java.util.StringTokenizer;
  7.  
  8. public class _17130 {
  9.  
  10.     static int N, M;
  11.     static int[][] arr;
  12.     static int[][] dp;
  13.     static int[] dy = { -1, 0, 1 }, dx = { -1, -1, -1 };
  14.  
  15.     public static void main(String[] args) throws IOException {
  16.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  17.         StringTokenizer st = new StringTokenizer(br.readLine());
  18.         N = Integer.parseInt(st.nextToken());
  19.         M = Integer.parseInt(st.nextToken());
  20.         arr = new int[N][M];
  21.         dp = new int[N][M];
  22.  
  23.         for (int i = 0; i < N; i++) // dp 모두 -1로 초기화
  24.             Arrays.fill(dp[i], -1);
  25.  
  26.         int sy = 0, sx = 0; // 시작점 저장
  27.         ArrayList<Loc> list = new ArrayList<Loc>(); // 종료 좌표 저장
  28.  
  29.         for (int i = 0; i < N; i++) {
  30.             String input = br.readLine();
  31.             for (int j = 0; j < M; j++) {
  32.                 char ch = input.charAt(j);
  33.                 int val = 0;
  34.                 if (ch == 'O') { // 종료지점일 경우
  35.                     list.add(new Loc(i, j));
  36.                     val = 2; // 배열이 2라면 그것은 종료지점
  37.                 } else if (ch == 'R') { // 시작점일 경우
  38.                     sy = i;
  39.                     sx = j;
  40.                     dp[sy][sx] = 0; // 시작좌표의 dp는 0으로 초기화
  41.                 } else if (ch == 'C') {
  42.                     val = 1;
  43.                 } else if (ch == '#') { // 가지 못하는 곳
  44.                     val = -1; // -1 이라면 접근 하지마
  45.                 }
  46.                 arr[i][j] = val;
  47.             }
  48.         }
  49.  
  50.         // 시작좌표의 같은 열에 있는 좌표들을 접근을 못하고 다른 좌표에서 참조하지 않도록 -1로 초기화
  51.         for (int i = 0; i < N; i++) {
  52.             if (i == sy)
  53.                 continue;
  54.             arr[i][sx] = -1;
  55.         }
  56.  
  57.         // ARR 배열 확인용 - 지워야함
  58.         System.out.println("ARR배열 체크");
  59.         for (int i = 0; i < N; i++) {
  60.             for (int j = 0; j < M; j++) {
  61.                 System.out.printf("%2d ", arr[i][j]);
  62.             }
  63.             System.out.println();
  64.         }
  65.         System.out.println();
  66.  
  67.         boolean flag = false; // 종료지점에 도달하였는지에 대한 플래그 변수
  68.  
  69.         // 시작좌표의 다음 열부터 체크, 한 열에서 모든 행을 체크 후 오른쪽 열으로 이동
  70.         for (int j = sx + 1; j < M; j++) {
  71.             for (int i = 0; i < N; i++) {
  72.                 if (arr[i][j] == -1) // 본 배열에 -1 일 경우 그냥 바로 탈출(벽일 경우)
  73.                     continue;
  74.                 // . O C 일 경우 일단 확인을 해보자
  75.                 int max = -1; // 이전 좌표가 있었는지에 확인하고 이전 dp 최대값 저장할 변수
  76.                 for (int d = 0; d < 3; d++) { // ←, ↙, ↖ 방향 확인
  77.                     int y = i + dy[d];
  78.                     int x = j + dx[d];
  79.                     if (0 <= y && y < N && 0 <= x) {
  80.                         // dp가 -1일 경우 그냥 바로 다음거 확인 || 이전이 종료지점이였으면 continue
  81.                         if (dp[y][x] == -1 || arr[y][x] == 2)
  82.                             continue;
  83.                         max = Math.max(max, dp[y][x]);
  84.                     }
  85.                 }
  86.                 //  ** 조언대로 고친 부분 **
  87.                 if (max != -1) { // 이전 좌표에서 접근 했다라면 dp를 최신화
  88.                     // 고침으로써 당근이 있었더라도 이전에서 접근하지 않았다면 dp 값을 -1로 그대로 놔둠
  89.                     if (arr[i][j] == 2) { // 종료지점이라면 dp를 0으로 초기화
  90.                         dp[i][j] = max;
  91.                     } else if (arr[i][j] == 0 || arr[i][j] == 1) {
  92.                         dp[i][j] = arr[i][j] + max;
  93.                     }
  94.                     if (arr[i][j] == 2 && dp[i][j] != -1) { // 만약 접근을 했고 이것이 종료지점이라면 플래그 변수를 true
  95.                         flag = true;
  96.                     }
  97.                 }
  98.             }
  99.         }
  100.  
  101.         int ret = 0;
  102.  
  103.         // 종료 좌표들의 dp를 확인하면서 최대값을 찾는다.
  104.         for (int i = 0; i < list.size(); i++) {
  105.             ret = Math.max(ret, dp[list.get(i).y][list.get(i).x]);
  106.         }
  107.  
  108. //       DP 배열 확인용 - 지워야함
  109.         System.out.println("DP배열 체크");
  110.         for (int i = 0; i < N; i++) {
  111.             for (int j = 0; j < M; j++) {
  112.                 System.out.printf("%2d ", dp[i][j]);
  113.             }
  114.             System.out.println();
  115.         }
  116.  
  117. //input
  118. //3 4
  119. //.##O
  120. //R#CO
  121. //.##O
  122.  
  123.         if (!flag)
  124.             System.out.println(-1);
  125.         else
  126.             System.out.println(ret);
  127.  
  128.         br.close();
  129.     }
  130.  
  131.     static class Loc {
  132.         int y, x;
  133.  
  134.         Loc(int y, int x) {
  135.             this.y = y;
  136.             this.x = x;
  137.         }
  138.     }
  139.  
  140. }
Add Comment
Please, Sign In to add comment