글 읽기 - bfs... 반례좀 부탁드립니다.

pineleaf1215 6년 전 0

bfs로 풀었는데 왠만한 예시들은 다되는거 같은데 반례좀 부탁드립니다...

그리고

1 1

이여서 출발하자마자 도착인경우는 발걸음수가 0 이니까 0 이맞겠죠?

#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;		
	
		if( r ==R-1)
			return;

	
		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 &&r-ways[k].r != 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;

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

bfs... 반례좀 부탁드립니다.

pineleaf1215 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말