結果

問題 No.424 立体迷路
ユーザー thaim24thaim24
提出日時 2016-09-22 23:32:14
言語 Java
(openjdk 23)
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 3,299 bytes
コンパイル時間 3,784 ms
コンパイル使用メモリ 84,312 KB
実行使用メモリ 41,772 KB
最終ジャッジ日時 2024-07-05 07:06:57
合計ジャッジ時間 7,962 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class No424 {
static final int[][] move = {
{0, 1},
{-1, 0},
{0, -1},
{1, 0}
};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int h = sc.nextInt();
int w = sc.nextInt();
int[] pos = new int[4];
pos[0] = sc.nextInt();
pos[1] = sc.nextInt();
pos[2] = sc.nextInt();
pos[3] = sc.nextInt();
String[] b = new String[h];
for (int i=0; i<h; i++) {
b[i] = sc.next();
}
int[][] board = new int[h+2][w+2];
for (int i=1; i<=h; i++) {
for (int j=1; j<=w; j++) {
board[i][j] = b[i-1].charAt(j-1) - '0';
}
}
String result = solve(h, w, pos, board);
System.out.println(result);
}
public static String solve(int h, int w, int[] pos, int[][] board) {
boolean[][] reachable = new boolean[h+2][w+2];
reachable[pos[0]][pos[1]] = true;
List<Pos> list = new ArrayList<Pos>();
list.add(new Pos(pos[0], pos[1]));
while (!reachable[pos[2]][pos[3]] && list.size() > 0) {
Pos current = list.remove(0);
// System.err.println("current:" + current.toString());
for (int i=0; i<4; i++) {
Pos next = new Pos(current.x + move[i][0], current.y + move[i][1]);
Pos next2 = new Pos(next.x + move[i][0], next.y + move[i][1]);
// System.err.println("\tmove:" + move[i][0] + ", " + move[i][1] + ", next:" + next + ", next2:" + next2);
if (next.x> h || next.x == 0
|| next.y > w
|| next.y == 0) {
continue;
}
// System.err.println("\tcheck start");
if (!reachable[next.x][next.y] &&
Math.abs(board[current.x][current.y]-board[next.x][next.y]) <= 1) {
reachable[next.x][next.y] = true;
// System.err.println("\tboard: current=" + board[current.x][current.y] + ", next=" + board[next.x][next.y]);
list.add(next);
// System.err.println(next);
}
// System.err.println("\tcheck2 start");
if (board[current.x][current.y] > board[next.x][next.y]
&& next2.x <= h && next2.x > 0
&& next2.y <= w && next2.y > 0
&& !reachable[next2.x][next2.y]
&& board[current.x][current.y] == board[next2.x][next2.y]) {
reachable[next2.x][next2.y] = true;
list.add(new Pos(next2.x, next2.y));
// System.err.println(next2);
}
}
}
if (reachable[pos[2]][pos[3]]) {
return "YES";
} else {
return "NO";
}
}
public static class Pos {
int x;
int y;
public Pos(int a, int b) {
x = a;
y = b;
}
public String toString() {
return "(" + x + ", " + y + ")";
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0