Guest User

noanswer

a guest
Apr 10th, 2019
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.54 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.         boolean flag = false; // 종료지점에 도달하였는지에 대한 플래그 변수
  58.  
  59.         // 시작좌표의 다음 열부터 체크, 한 열에서 모든 행을 체크 후 오른쪽으로 이동
  60.         for (int j = sx + 1; j < M; j++) {
  61.             for (int i = 0; i < N; i++) {
  62.                 if (arr[i][j] == -1) // 본 배열에 -1 일 경우 그냥 바로 탈출(확인 안해도 되니까)
  63.                     continue;
  64.                 dp[i][j] = arr[i][j]; // 당근이 있다면 1로 초기화하고
  65.                 if (arr[i][j] == 2) // 종료지점이라면 원배열은 2로 되있는데 dp에는 0으로
  66.                     dp[i][j] = 0;
  67.  
  68.                 int max = -1; // 이전 좌표가 있었는지에 확인하고 이전 dp에서 최대값 저장
  69.                 for (int d = 0; d < 3; d++) { // ←, ↙, ↖ 방향 확인
  70.                     int y = i + dy[d];
  71.                     int x = j + dx[d];
  72.                     if (0 <= y && y < N && 0 <= x) {
  73.                         if (dp[y][x] < 0) // dp가 -1일 경우 그냥 바로 다음거 확인
  74.                             continue;
  75.                         max = Math.max(max, dp[y][x]);
  76.                     }
  77.                 }
  78.                 if (max >= 0) { // 이전 좌표에서 접근 했다라면 dp를 최신화
  79.                     dp[i][j] += max;
  80.                     if (arr[i][j] == 2) { // 만약 접근을 했고 이것이 종료지점이라면 플래그 변수를 true
  81.                         flag = true;
  82.                     }
  83.                 }
  84.             }
  85.         }
  86.  
  87.         int ret = 0;
  88.  
  89.         // 종료 좌표들의 dp를 확인하면서 최대값을 찾는다.
  90.         for (int i = 0; i < list.size(); i++) {
  91.             ret = Math.max(ret, dp[list.get(i).y][list.get(i).x]);
  92.         }
  93.  
  94.         // DP 배열 확인용 - 지워야함
  95. //      System.out.println("DP배열 체크");
  96. //      for (int i = 0; i < N; i++) {
  97. //          for (int j = 0; j < M; j++) {
  98. //              System.out.printf("%2d ", dp[i][j]);
  99. //          }
  100. //          System.out.println();
  101. //      }
  102.  
  103.         if (!flag)
  104.             System.out.println(-1);
  105.         else
  106.             System.out.println(ret);
  107.  
  108.         br.close();
  109.     }
  110.  
  111.     static class Loc {
  112.         int y, x;
  113.  
  114.         Loc(int y, int x) {
  115.             this.y = y;
  116.             this.x = x;
  117.         }
  118.     }
  119.  
  120. }
Advertisement
Add Comment
Please, Sign In to add comment