#include <stdio.h>
int n/*높이*/,m/*너비*/;
int map[1002][1002]={},rode[1002][1002]={};
int queue[1000001][2]={},qu = 0,de = 0;
int foot = 1;
int x,y;
void push(int a,int b){
if(b<0||a<0||b>=m||a>=n) return ;
if(rode[a][b]==1) return ;
if(map[y][x]-1 > map[a][b] || map[y][x]+1 < map[a][b]) return ;
queue[++qu][0]=a;
queue[qu][1]=b;
rode[a][b]=1;
}
int main(){
scanf("%d %d",&n,&m);
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
scanf("%d",&map[i][j]);
}
}
push(0,0);
int max;
while(rode[n-1][m-1]==0){
foot++;
max = qu;
for(int i = de+1 ; i <= max ; i++){
de++;
y=queue[i][0],x=queue[i][1];
push(y+1,x);
push(y-1,x);
push(y,x+1);
push(y,x-1);
if( qu == de ){printf("0"); return ;}
}
}
printf("%d",foot);
return 0;
}
top of page

기능을 테스트하려면 라이브 사이트로 이동하세요.
수정: 2023년 12월 10일
BFS 놀이공원
BFS 놀이공원
댓글 0개
좋아요
댓글(0)
bottom of page