結果
問題 | No.367 ナイトの転身 |
ユーザー | jp_ste |
提出日時 | 2016-05-12 19:21:28 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 589 ms / 2,000 ms |
コード長 | 4,064 bytes |
コンパイル時間 | 4,054 ms |
コンパイル使用メモリ | 78,992 KB |
実行使用メモリ | 72,632 KB |
最終ジャッジ日時 | 2024-04-15 15:23:19 |
合計ジャッジ時間 | 11,823 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 149 ms
54,560 KB |
testcase_01 | AC | 150 ms
54,360 KB |
testcase_02 | AC | 144 ms
54,108 KB |
testcase_03 | AC | 150 ms
54,508 KB |
testcase_04 | AC | 152 ms
54,332 KB |
testcase_05 | AC | 143 ms
54,276 KB |
testcase_06 | AC | 184 ms
54,112 KB |
testcase_07 | AC | 146 ms
54,224 KB |
testcase_08 | AC | 151 ms
54,492 KB |
testcase_09 | AC | 149 ms
54,348 KB |
testcase_10 | AC | 526 ms
68,828 KB |
testcase_11 | AC | 589 ms
72,632 KB |
testcase_12 | AC | 301 ms
60,140 KB |
testcase_13 | AC | 313 ms
60,088 KB |
testcase_14 | AC | 411 ms
60,516 KB |
testcase_15 | AC | 196 ms
54,184 KB |
testcase_16 | AC | 398 ms
60,408 KB |
testcase_17 | AC | 278 ms
57,896 KB |
testcase_18 | AC | 244 ms
57,812 KB |
testcase_19 | AC | 296 ms
58,816 KB |
testcase_20 | AC | 197 ms
56,360 KB |
testcase_21 | AC | 293 ms
58,196 KB |
testcase_22 | AC | 160 ms
54,948 KB |
testcase_23 | AC | 158 ms
54,980 KB |
testcase_24 | AC | 167 ms
54,528 KB |
testcase_25 | AC | 167 ms
54,836 KB |
testcase_26 | AC | 157 ms
54,524 KB |
ソースコード
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main2 { static int h,w; static char list[][]; static int dp[][][]; static int goalX, goalY; static final int NIGHT = 0; static final int BISHOP = 1; static int nDirX[] = { 1, 1, -1, -1, 2, 2, -2, -2 }; static int nDirY[] = { 2, -2, 2, -2, 1, -1, 1, -1 }; static int bDirX[] = { 1, 1, -1, -1 }; static int bDirY[] = { 1, -1, 1, -1 }; public static void main(String[] args) { try (Scanner scan = new Scanner(System.in)) { h = Integer.parseInt(scan.next()); w = Integer.parseInt(scan.next()); list = new char[h][w]; dp = new int[h][w][2]; int startX = 0, startY = 0; for(int i=0; i<h; i++) { String line = scan.next(); for(int j=0; j<w; j++) { char ch = line.charAt(j); list[i][j] = ch; if(ch == 'G') { goalX = j; goalY = i; } else if(ch == 'S') { startX = j; startY = i; } for(int k=0; k<2; k++) { dp[i][j][k] = Integer.MAX_VALUE; } } } solve(startX, startY); System.out.println(-1); } } static void solve(int startX, int startY) { Queue<Node> q = new LinkedList<>(); Node s = new Node(startX, startY, 0, NIGHT); q.add(s); while(!q.isEmpty()) { Node now = q.poll(); if(now.x == goalX && now.y == goalY) { System.out.println(now.steps); System.exit(0); } if(now.state == NIGHT) { if(dp[now.y][now.x][NIGHT] > now.steps) { dp[now.y][now.x][NIGHT] = now.steps; } else { continue; } } else { if(dp[now.y][now.x][BISHOP] > now.steps) { dp[now.y][now.x][BISHOP] = now.steps; } else { continue; } } if(now.state == NIGHT) { for(int i=0; i<8; i++) { int nextX = now.x + nDirX[i]; int nextY = now.y + nDirY[i]; if(nextX >= 0 && nextX <= w-1 && nextY >= 0 && nextY <= h-1 ) { int nextState = now.state; if(list[nextY][nextX] == 'R') { nextState = BISHOP; } Node next = new Node(nextX, nextY, now.steps+1, nextState); q.add(next); } } } else if(now.state == BISHOP) { for(int i=0; i<4; i++) { int nextX = now.x + bDirX[i]; int nextY = now.y + bDirY[i]; if(nextX >= 0 && nextX <= w-1 && nextY >= 0 && nextY <= h-1 ) { int nextState = now.state; if(list[nextY][nextX] == 'R') { nextState = NIGHT; } Node next = new Node(nextX, nextY, now.steps+1, nextState); q.add(next); } } } } } } class Node { int x, y; int steps; int state; Node(int x, int y, int steps, int state) { this.x = x; this.y = y; this.steps = steps;; this.state = state; } }