Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.ArrayList;
- import java.util.Arrays;
- import java.util.StringTokenizer;
- public class _17130 {
- static int N, M;
- static int[][] arr;
- static int[][] dp;
- static int[] dy = { -1, 0, 1 }, dx = { -1, -1, -1 };
- public static void main(String[] args) throws IOException {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- StringTokenizer st = new StringTokenizer(br.readLine());
- N = Integer.parseInt(st.nextToken());
- M = Integer.parseInt(st.nextToken());
- arr = new int[N][M];
- dp = new int[N][M];
- for (int i = 0; i < N; i++) // dp 모두 -1로 초기화
- Arrays.fill(dp[i], -1);
- int sy = 0, sx = 0; // 시작점 저장
- ArrayList<Loc> list = new ArrayList<Loc>(); // 종료 좌표 저장
- for (int i = 0; i < N; i++) {
- String input = br.readLine();
- for (int j = 0; j < M; j++) {
- char ch = input.charAt(j);
- int val = 0;
- if (ch == 'O') { // 종료지점일 경우
- list.add(new Loc(i, j));
- val = 2; // 배열이 2라면 그것은 종료지점
- } else if (ch == 'R') { // 시작점일 경우
- sy = i;
- sx = j;
- dp[sy][sx] = 0; // 시작좌표의 dp는 0으로 초기화
- } else if (ch == 'C') {
- val = 1;
- } else if (ch == '#') { // 가지 못하는 곳
- val = -1; // -1 이라면 접근 하지마
- }
- arr[i][j] = val;
- }
- }
- // 시작좌표의 같은 열에 있는 좌표들을 접근을 못하고 다른 좌표에서 참조하지 않도록 -1로 초기화
- for (int i = 0; i < N; i++) {
- if (i == sy)
- continue;
- arr[i][sx] = -1;
- }
- boolean flag = false; // 종료지점에 도달하였는지에 대한 플래그 변수
- // 시작좌표의 다음 열부터 체크, 한 열에서 모든 행을 체크 후 오른쪽으로 이동
- for (int j = sx + 1; j < M; j++) {
- for (int i = 0; i < N; i++) {
- if (arr[i][j] == -1) // 본 배열에 -1 일 경우 그냥 바로 탈출(확인 안해도 되니까)
- continue;
- dp[i][j] = arr[i][j]; // 당근이 있다면 1로 초기화하고
- if (arr[i][j] == 2) // 종료지점이라면 원배열은 2로 되있는데 dp에는 0으로
- dp[i][j] = 0;
- int max = -1; // 이전 좌표가 있었는지에 확인하고 이전 dp에서 최대값 저장
- for (int d = 0; d < 3; d++) { // ←, ↙, ↖ 방향 확인
- int y = i + dy[d];
- int x = j + dx[d];
- if (0 <= y && y < N && 0 <= x) {
- if (dp[y][x] < 0) // dp가 -1일 경우 그냥 바로 다음거 확인
- continue;
- max = Math.max(max, dp[y][x]);
- }
- }
- if (max >= 0) { // 이전 좌표에서 접근 했다라면 dp를 최신화
- dp[i][j] += max;
- if (arr[i][j] == 2) { // 만약 접근을 했고 이것이 종료지점이라면 플래그 변수를 true
- flag = true;
- }
- }
- }
- }
- int ret = 0;
- // 종료 좌표들의 dp를 확인하면서 최대값을 찾는다.
- for (int i = 0; i < list.size(); i++) {
- ret = Math.max(ret, dp[list.get(i).y][list.get(i).x]);
- }
- // DP 배열 확인용 - 지워야함
- // System.out.println("DP배열 체크");
- // for (int i = 0; i < N; i++) {
- // for (int j = 0; j < M; j++) {
- // System.out.printf("%2d ", dp[i][j]);
- // }
- // System.out.println();
- // }
- if (!flag)
- System.out.println(-1);
- else
- System.out.println(ret);
- br.close();
- }
- static class Loc {
- int y, x;
- Loc(int y, int x) {
- this.y = y;
- this.x = x;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment