#include<stdio.h>
#define MAX 1002
#define LEN 1000000
int rear=0,front=0;
int mat[MAX][MAX];
int mem[MAX][MAX];
int R,C,N;
typedef struct{
int r,c;
}Q;
Q que[LEN];
Q que_temp[LEN];
Q ways[10];
void enque(int r,int c){
rear++;
que[rear].r = r;
que[rear].c = c;
};
Q deque(){
return que[front++];
};
void ini(){
int i,j;
for(i=front;i<=rear;i++)
que_temp[i-front] = que[i];
for(i=0;i<= rear-front;i++)
que[i] = que_temp[i];
front = 0;
rear = rear-front;
}
void bfs(){
int i,j;
Q temp;
int k=0;
int r,c;
while( front <= rear){
temp = deque();
r = temp.r;
c = temp.c;
k=0;
while( k <N ){
if( r-ways[k].r>=0 && r-ways[k].r <R && c+ways[k].c>=0 && c+ways[k].c<C ) //도로 밖으로 나가지 않게
if(mat[r-ways[k].r][c+ways[k].c] ==1 && mem[r-ways[k].r][c+ways[k].c] == 0){
//이동 거리측정.
if(( mem[r-ways[k].r][c+ways[k].c] >= mem[r][c] + 1) || (mem[r-ways[k].r][c+ways[k].c]==0) ){
mem[r-ways[k].r][c+ways[k].c] = mem[r][c]+1;
enque( r-ways[k].r , c+ways[k].c );
if(rear == LEN)
ini();
}
}
k++;
}
}
}
int main(){
int i,j;
int min2 = MAX*MAX;
int flag =0;
Q temp;
//초기화
scanf("%d %d",&R,&C);
for(i=0;i<R;i++){
for(j=0;j<C;j++){
scanf("%d",&mat[i][j]);
if(R == 1 && mat[0][j] ==1){
flag =1;
}
}
}
for(i=0;i<R;i++)
for(j=0;j<C;j++)
mem[i][j] = 0;
scanf("%d",&N);
for(i=0;i<N;i++)
scanf("%d %d",&ways[i].r ,&ways[i].c);
if(flag == 1){
printf("%d",0);
return 0;
}
for(i=0;i<C;i++)
if(mat[0][i] == 1)
enque(0,i);
bfs();
for(i=0;i<C;i++)
if( mem[R-1][i] < min2 && mem[R-1][i] != 0){
min2 = mem[R-1][i];
flag =1;
}
if( flag == 0 )
min2 = -1;
printf("%d", min2);
return 0;
}
bfs로 풀었는데, 아직 반례를 찾지 못했습니다.. 틀렸다고나옵니다. 도와주세요...
bfs에다가 , 다익스트라?를 나름 적용했습니다.
mem[i][j] 행렬에다가 i,j까지 가는 최단경로를 저장했습니다..
글쓰기