글 읽기 - 대체 왜 틀렸을까요? ㅠㅠㅠㅠㅠ

dreammusic23 8년 전 0

우선 각 대륙(만약 물로 갈라졌다면)마다 아무 땅 좌표에서 bfs를 돌려서 그 대륙에서의 최대 거리를 찾습니다.

(chk1[0]에 거리를 표시, chk1[1]에 대륙번호를 표시)

그리고 그 최대 거리인 점에서 bfs를 돌려서 그 점으로부터 걸리는 시간을 찾아줍니다.

(chk2에 저장하고, 이걸 각 대륙마다 반복합니다)

어짜피 각 대륙마다 1부터 적혀있을 것이므로 지도 전체에서 최댓값-1을 출력합니다.

정말 잘 돌아가는데 어디서 어떻게 틀린걸까요 ㅠㅠㅠㅠ

여러가지 케이스를 돌려보았으나... 찾을 수 없었습니다 ㅠㅠ

도와주세요 고수님들 ㅠㅠ

#include "stdio.h"
char map[55][55]={0};
int chk1[2][55][55]={0},chk2[55][55]={0},count=0,xx,yy;
int queue[2][2505]={0},front,rear;
void bfs1(int i,int j,int n,int m){
	int x,y;
	while(front<rear){
		x=queue[0][front];
		y=queue[1][front++];
		if(x+1<n&&map[x+1][y]=='L'&&!chk1[0][x+1][y]){
			chk1[0][x+1][y]=chk1[0][x][y]+1;
			chk1[1][x+1][y]=count;
			queue[0][rear]=x+1;
			queue[1][rear++]=y;
		}
		if(x>0&&map[x-1][y]=='L'&&!chk1[0][x-1][y]){
			chk1[0][x-1][y]=chk1[0][x][y]+1;
			chk1[1][x-1][y]=count;
			queue[0][rear]=x-1;
			queue[1][rear++]=y;
		}
		if(y+1<m&&map[x][y+1]=='L'&&!chk1[0][x][y+1]){
			chk1[0][x][y+1]=chk1[0][x][y]+1;
			chk1[1][x][y+1]=count;
			queue[0][rear]=x;
			queue[1][rear++]=y+1;
		}
		if(y>0&&map[x][y-1]=='L'&&!chk1[0][x][y-1]){
			chk1[0][x][y-1]=chk1[0][x][y]+1;
			chk1[1][x][y-1]=count;
			queue[0][rear]=x;
			queue[1][rear++]=y-1;
		}
	}
}
void bfs2(int i,int j,int n,int m){
	int x,y;
	while(front<rear){
		x=queue[0][front];
		y=queue[1][front++];
		if(x+1<n&&map[x+1][y]=='L'&&!chk2[x+1][y]){
			chk2[x+1][y]=chk2[x][y]+1;
			queue[0][rear]=x+1;
			queue[1][rear++]=y;
		}
		if(x>0&&map[x-1][y]=='L'&&!chk2[x-1][y]){
			chk2[x-1][y]=chk2[x][y]+1;
			queue[0][rear]=x-1;
			queue[1][rear++]=y;
		}
		if(y+1<m&&map[x][y+1]=='L'&&!chk2[x][y+1]){
			chk2[x][y+1]=chk2[x][y]+1;
			queue[0][rear]=x;
			queue[1][rear++]=y+1;
		}
		if(y>0&&map[x][y-1]=='L'&&!chk2[x][y-1]){
			chk2[x][y-1]=chk2[x][y]+1;
			queue[0][rear]=x;
			queue[1][rear++]=y-1;
		}
	}
}
int main(){
	int x,y,i,j,k,MAX=0;
	scanf("%d %d",&x,&y);
	for(i=0;i<x;i++) scanf("%s",map[i]);
	for(i=0;i<x;i++) for(j=0;j<y;j++){
		if(map[i][j]=='L'&&!chk1[0][i][j]){
			front=0,rear=0;
			chk1[0][i][j]=1;
			chk1[1][i][j]=++count;
			queue[0][rear]=i;
			queue[1][rear++]=j;
			bfs1(i,j,x,y);
		}
	}
	for(k=1;k<=count;k++){
		int max=0;
		for(i=0;i<x;i++) for(j=0;j<y;j++){
			if(chk1[1][i][j]==k&&max<chk1[0][i][j]){
				max=chk1[0][i][j];
				xx=i,yy=j;
			}
		}
		front=0,rear=0;
		chk2[xx][yy]=1;
		queue[0][rear]=xx;
		queue[1][rear++]=yy;
		bfs2(xx,yy,x,y);
	}
	for(i=0;i<x;i++) for(j=0;j<y;j++) if(MAX<chk2[i][j]) MAX=chk2[i][j];
	printf("%d\n",MAX-1);
	/* 대륙별로 가장 먼 정점이 어딘지 찾아 봄
	for(i=0;i<x;i++){
		for(j=0;j<y;j++){
			printf("%d ",chk1[0][i][j]);
		}
		printf("\n");
	}
	*/
	/* 대륙마다 제대로 체크 되었는지 확인
	for(i=0;i<x;i++){
		for(j=0;j<y;j++){
			printf("%d ",chk1[1][i][j]);
		}
		printf("\n");
	}
	*/
	/* 최대 거리에서의 시간 출력
	for(i=0;i<x;i++){
		for(j=0;j<y;j++){
			printf("%d ",chk2[i][j]);
		}
		printf("\n");
	}
	*/
	return 0;
}

dreammusic23 8년 전 1

모든 점에서 돌려야 하는군요 ㅠ

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

문제

문제

출처

ICPC

대체 왜 틀렸을까요? ㅠㅠㅠㅠㅠ

dreammusic23 8년 전 0

dreammusic23 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말