結果
問題 | No.124 門松列(3) |
ユーザー |
|
提出日時 | 2016-05-01 17:17:19 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,149 bytes |
コンパイル時間 | 1,894 ms |
コンパイル使用メモリ | 78,516 KB |
実行使用メモリ | 58,208 KB |
最終ジャッジ日時 | 2024-10-05 00:36:31 |
合計ジャッジ時間 | 7,501 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 22 WA * 4 |
ソースコード
package yukicoder;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Queue;import java.util.Scanner;public class Main{public static void main(String[] args)throws Exception{new Main().solve();}void solve(){Scanner sc=new Scanner(System.in);int w=sc.nextInt();int h=sc.nextInt();int[][] table=new int[h][w];for(int i=0;i<h;i++){for(int j=0;j<w;j++){table[i][j]=sc.nextInt();}}BFS bfs=new BFS(table);int ans=bfs.bfs(0, 0, w-1, h-1);System.out.println(ans);}int[] dx={1,-1,0,0};int[] dy={0,0,-1,1};class BFS{Queue<Vertice> q;final long INF=Long.MAX_VALUE/4;int[][] table;int w,h;boolean[][] arrived;BFS(int[][] table){h=table.length;w=table[0].length;this.table=new int[h][w];for(int i=0;i<h;i++){for(int j=0;j<w;j++){this.table[i][j]=table[i][j];}}q=new ArrayDeque<Vertice>(h*w);arrived=new boolean[h][w];}int bfs(int sx,int sy,int gx,int gy){q.add(new Vertice(sx,sy,-1,-1,-1,-1,-1,-1,0));int ans=-1;while(!q.isEmpty()){Vertice v=q.poll();if(v.x==gx&&v.y==gy){ans=v.d;break;}for(int i=0;i<4;i++){int nx=v.x+dx[i];int ny=v.y+dy[i];if(nx<0||ny<0||nx>=w||ny>=h)continue;if(arrived[ny][nx])continue;if(v.d>=1){if(!isKadomatsu(table[ny][nx],table[v.y][v.x],table[v.y1][v.x1])){continue;}}q.add(new Vertice(nx,ny,v.x,v.y,v.x1,v.y1,v.x2,v.y2, v.d+1));if(v.d>=1)arrived[ny][nx]=true;}}return ans;}}class Vertice{int x;int y;int d;int x1,y1,x2,y2,x3,y3;//(x1,y1)は一つ前の座標、(x2,y2)は二つ前の座標Vertice(int x,int y,int x1,int y1,int x2,int y2,int x3,int y3,int d){this.x=x;this.y=y;this.d=d;this.x1=x1;this.y1=y1;this.x2=x2;this.y2=y2;this.x3=x3;this.y3=y3;}}boolean isKadomatsu(int n1,int n2,int n3){if(n2>n1&&n2>n3&&n1!=n3){return true;}else if(n2<n1&&n2<n3&&n1!=n3){return true;}else {return false;}}void tr(Object...o){System.out.println(Arrays.deepToString(o));}}