글 읽기 - (소스+주석) 왜 틀렸는지 모르겠네요.

kons 8년 전 0

기본적인 생각은 일단 고슴도치와 물을 각각 BFS돌렸어요.

물 먼저 BFS 돌려서 언제 그 칸에 물이 도착하는지를 starL[51][51]에 저장을 한 후,

고슴도치 BFS를 돌려서 물이 오기전에 그 칸에 도착하면 갈수잇도록 진행하였습니다.

몇가지 예제를 만들어서 돌려봐도 잘 되는데, 틀렸습니다 가 뜹니다.

혹시 어느 부분이 잘못됬는지 아시는 분 계신가요?

#include<stdio.h>

int R,C;
int Sfront,star_front;
int Srear,star_rear;
char A[51][51];
char B[51][51];
int S[2],D[2],star[2];
int SQ[2600][2];
int SL[51][51];
int starL[51][51];
int starQ[2600][2];

void bfs();
void starbfs();
int main(void){
	
	scanf("%d %d",&R,&C);
	for (int i = 1; i <=R; i++)
            scanf("%s", A[i]);

	for(int i=1;i<=R;i++){
		for(int j=C;j>=1;j--){
				A[i][j] = A[i][j-1];
				B[i][j]=A[i][j];
				if(A[i][j]=='D'){D[0]=i;D[1]=j;}
				else if(A[i][j]=='S'){S[0]=i;S[1]=j;}
				else if(A[i][j]=='*'){star[0]=i;star[1]=j;}
		}
	}

	for(int i=1;i<=R;i++){
		for(int j=1;j<=C;j++){
			printf("%c",A[i][j]);
		}
		printf("\n");
	}


	SQ[1][0] = S[0];//x
	SQ[1][1] = S[1];//y
	SL[S[0]][S[1]] = 0;//S level
	starQ[1][0] = star[0];// star x
	starQ[1][1] = star[1];//star y 
	starL[star[0]][star[1]] = 0;//star level

	A[S[0]][S[1]] = '*';
	
	starbfs();
	
	for(int i=1;i<=R;i++){
		for(int j=1;j<=C;j++){
			printf("%2d",starL[i][j]);
		}
		printf("\n");
	}

	getchar();
	
	bfs();
	
	for(int i=1;i<=R;i++){
		for(int j=1;j<=C;j++){
			printf("%2d",SL[i][j]);
		}
		printf("\n");
	}

	if(SL[D[0]][D[1]]!=0)
		printf("%d",SL[D[0]][D[1]]);
	else
		printf("KAKTUS");
	
	getchar();getchar();
	
	return 0;
}

void starbfs(){
	int x,y;
	star_front =1;
	star_rear = 2;

	while(star_front<=star_rear){
		
		x = starQ[star_front][0];
		y = starQ[star_front][1];
		star_front++;

		if( ((y+1)<=C) && (B[x][y+1]!='*') && (B[x][y+1]!='X') && (B[x][y+1]!='D')){
			B[x][y+1]='*';//한번왓던길은 그냥 못가니까 *로 해버림.
			starQ[star_rear][0] = x;
			starQ[star_rear][1] = y+1;
			starL[x][y+1] = starL[x][y]+1;
			star_rear++;
		}
		
		if( ((y-1)>=1) && (B[x][y-1]!='*') && (B[x][y-1]!='X') && (B[x][y-1]!='D')){
			B[x][y-1]='*';
			starQ[star_rear][0] = x;
			starQ[star_rear][1] = y-1;
			starL[x][y-1] = starL[x][y]+1;
			star_rear++;
		}
		if( ((x+1)<=R) && (B[x+1][y]!='*') && (B[x+1][y]!='X') && (B[x+1][y]!='D')){
			B[x+1][y]='*';
			starQ[star_rear][0] = x+1;
			starQ[star_rear][1] = y;
			starL[x+1][y] = starL[x][y]+1;
			star_rear++;
		}
		
		if( ((x-1)>=1) && (B[x-1][y]!='*') && (B[x-1][y]!='X') && (B[x-1][y]!='D')){
			B[x-1][y]='*';//한번왓던길은 그냥 못가니까 *로 해버림.
			starQ[star_rear][0] = x-1;
			starQ[star_rear][1] = y;
			starL[x-1][y] = starL[x][y]+1;
			star_rear++;
		}
	}


}

void bfs(){
	int x,y;
	Sfront =1;
	Srear = 2;

	while(Sfront<=Srear){
		
		x = SQ[Sfront][0];
		y = SQ[Sfront][1];
		Sfront++;

		if(x==D[0] && y==D[1]){return;}

		if( ((y+1)<=C) && (A[x][y+1]!='*')&& (A[x][y+1]!='X') && ((starL[x][y+1]>(SL[x][y]+1))||starL[x][y+1]==0) ){
			A[x][y+1]='*';//한번왓던길은 그냥 못가니까 *로 해버림.
			SQ[Srear][0] = x;
			SQ[Srear][1] = y+1;
			SL[x][y+1] = SL[x][y]+1;
			Srear++;
		}
		if( ((y-1)>=1) && (A[x][y-1]!='*')&& (A[x][y-1]!='X')&& ((starL[x][y-1]>(SL[x][y]+1))||starL[x][y-1]==0)  ){
			A[x][y-1]='*';//한번왓던길은 그냥 못가니까 *로 해버림.
			SQ[Srear][0] = x;
			SQ[Srear][1] = y-1;
			SL[x][y-1] = SL[x][y]+1;
			Srear++;
		}
		if( ((x+1)<=R) && (A[x+1][y]!='*')&& (A[x+1][y]!='X')&&( (starL[x+1][y]>(SL[x][y]+1))||starL[x+1][y]==0)  ){
			A[x+1][y]='*';//한번왓던길은 그냥 못가니까 *로 해버림.
			SQ[Srear][0] = x+1;
			SQ[Srear][1] = y;
			SL[x+1][y] = SL[x][y]+1;
			Srear++;
		}
		if( ((x-1)>=1) && (A[x-1][y]!='*')&& (A[x-1][y]!='X')&& ((starL[x-1][y]>(SL[x][y]+1))||starL[x-1][y]==0)  ){
			A[x-1][y]='*';//한번왓던길은 그냥 못가니까 *로 해버림.
			SQ[Srear][0] = x-1;
			SQ[Srear][1] = y;
			SL[x-1][y] = SL[x][y]+1;
			Srear++;
		}

	}


}

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

문제

문제

출처

ICPC

(소스+주석) 왜 틀렸는지 모르겠네요.

kons 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말