結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2016-09-28 16:36:14 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 79 ms / 2,000 ms |
コード長 | 2,921 bytes |
コンパイル時間 | 1,810 ms |
コンパイル使用メモリ | 78,920 KB |
実行使用メモリ | 39,096 KB |
最終ジャッジ日時 | 2024-07-05 07:10:56 |
合計ジャッジ時間 | 3,732 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
/* package whatever; // don't place package name! */import java.util.*;import java.lang.*;import java.io.*;/* Name of the class has to be "Main" only if the class is public. */class Ideone{public static void main (String[] args) throws java.lang.Exception{// your code goes hereBufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] lines = br.readLine().split(" ");int h = Integer.parseInt(lines[0]);int w = Integer.parseInt(lines[1]);lines = br.readLine().split(" ");int sh = Integer.parseInt(lines[0])-1;int sw = Integer.parseInt(lines[1])-1;int gh = Integer.parseInt(lines[2])-1;int gw = Integer.parseInt(lines[3])-1;int[][] map = new int[h][w];boolean[][] visit = new boolean[h][w];for(int i=0;i<h;i++){lines = br.readLine().split("");for(int j=0;j<w;j++){map[i][j] = Integer.parseInt(lines[j]);visit[i][j] = false;}}Deque<Pair> deq = new ArrayDeque<Pair>();Pair start = new Pair(sh,sw);Pair goal = new Pair(gh,gw);deq.add(start);visit[sh][sw] = true;start:while(!deq.isEmpty()){Pair p = deq.removeFirst();for(Pair next:getNext(map,p)){if(visit[next.h][next.w] == false){visit[next.h][next.w] = true;if(next.equals(goal)){break start;}deq.add(next);}}}System.out.println(visit[gh][gw]?"YES":"NO");}static private ArrayList<Pair> getNext(int[][] map,Pair p){int now_height = map[p.h][p.w];ArrayList<Pair> ret = new ArrayList<Pair>();for(Pair next:Pair.nexts){try{if(Math.abs(map[p.h+next.h][p.w+next.w] - now_height) <= 1){ret.add(new Pair(p.h+next.h,p.w+next.w));}if( map[p.h+next.h][p.w+next.w] < now_height&& map[p.h+next.h*2][p.w+next.w*2] == now_height){ret.add(new Pair(p.h+next.h*2,p.w+next.w*2));}}catch(Exception e){}}return ret;}private static class Pair{static Pair[] nexts = new Pair[]{new Pair(1,0),new Pair(0,1),new Pair(-1,0),new Pair(0,-1)};public int h;public int w;public Pair(int h,int w){this.h = h;this.w = w;}public boolean equals(Pair p){return this.h==p.h && this.w == p.w;}public String toString(){return new StringBuilder().append(h).append(",").append(w).toString();}}}