結果

問題 No.124 門松列(3)
ユーザー 37zigen
提出日時 2016-05-01 17:19:37
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 2,149 bytes
コンパイル時間 1,904 ms
コンパイル使用メモリ 78,972 KB
実行使用メモリ 57,872 KB
最終ジャッジ日時 2024-10-05 00:37:53
合計ジャッジ時間 7,179 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 22 WA * 4
権限があれば一括ダウンロードができます

ソースコード

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

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>=2)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));}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0