結果
問題 | No.367 ナイトの転身 |
ユーザー |
![]() |
提出日時 | 2016-05-12 19:21:28 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 464 ms / 2,000 ms |
コード長 | 4,064 bytes |
コンパイル時間 | 3,662 ms |
コンパイル使用メモリ | 78,524 KB |
実行使用メモリ | 60,692 KB |
最終ジャッジ日時 | 2024-10-05 14:04:55 |
合計ジャッジ時間 | 8,770 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
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; } }