結果

問題 No.124 門松列(3)
ユーザー 37zigen
提出日時 2016-05-01 17:08:49
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 2,163 bytes
コンパイル時間 2,961 ms
コンパイル使用メモリ 78,356 KB
実行使用メモリ 989,104 KB
最終ジャッジ日時 2024-10-05 00:36:51
合計ジャッジ時間 12,840 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample -- * 4
other MLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

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.d>=2){
if(!isKadomatsu(table[v.y][v.x],table[v.y1][v.x1],table[v.y2][v.x2])){
continue;
}
}
if(v.d>2){
arrived[v.y2][v.x2]=true;
}
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;
q.add(new Vertice(nx,ny,v.x,v.y,v.x1,v.y1,v.x2,v.y2, v.d+1));
}
}
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