글 읽기 - 탈출문제 도움부탁드립니다.

suleesulee 4년 전 0

예제들은 다 통과하는데

채점시작과 동시에 반례먹고 죽는것 같아요

코드한번 봐주시면 감사하겠습니다.

#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;
int map[50][50];
int r, c;
char in;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int sumdo_x[51];
int sumdo_y[51];
int terminate = 1;
int ter_x, ter_y;
int cond2 = 0;
int flag = 1;
int result = 0;

void flood_bfs(int x, int y)
{
	queue <pair<int, int>> q;
	q.push(make_pair(x, y));
	
	while(!q.empty()){
		x = q.front().first;
		y = q.front().second;
		q.pop();
		for(int k=0; k<4; k++){
			int nx = dx[k] + x;
			int ny = dy[k] + y;
			if(0<=nx && nx<r && 0<=ny && ny<c){
				if(map[nx][ny] == 0)
					map[nx][ny] = 3;
			}
		}
	}
}

void sumdo_bfs(int x, int y)
{
	queue <pair<int, int>> q;
	q.push(make_pair(x, y));
	
	x = q.front().first;
	y = q.front().second;
	q.pop();
	
	for(int k=0; k<4; k++){
		int nx = dx[k] + x;
		int ny = dy[k] + y;
		if(0<=nx && nx<r && 0<=ny && ny<c){
			if(map[nx][ny] == 0 || map[nx][ny] == -2)
				map[nx][ny] = -1;
		}
	}
}

void cond_bfs(int x, int y)
{
	queue <pair<int, int>> q;
	q.push(make_pair(x, y));
	
	x = q.front().first;
	y = q.front().second;
	q.pop();
	for(int k=0; k<4; k++){
		int nx = dx[k] + x;
		int ny = dy[k] + y;
		if(0<=nx && nx<r && 0<=ny && ny<c){
			if(map[nx][ny] == 1)
				cond2++;
		}
		else
			cond2++;
	}
}

int main()
{
	//input 
	for(int i=0; i<50; i++){
		for(int j=0; j<50; j++){
			map[i][j] = -4;
		}
	}

	scanf("%d %d", &r, &c);
	for(int i=0; i<r; i++){
		for(int j=0; j<c; j++){
			in = getchar();
			if(in == '\n')
				in = getchar();
			
			if(in == 'D'){
				map[i][j] = -2;
				ter_x = i;
				ter_y = j;
			}else if(in == '*'){
				map[i][j] = 1;
			}else if(in == 'S'){
				map[i][j] = -1;
			}else if(in == 'X'){
				map[i][j] = 2;
			}else if(in == '.'){
				map[i][j] = 0;
			}
		}
	}
	//test//
	// for(int i=0; i<r+2; i++){
	// 	for(int j=0; j<c+2; j++){
	// 		printf("%d", map[i][j]);
	// 	}
	// 	printf("\n");
	// }
	// printf("\n");
	//test//
	
	//반복
	while(flag){
		//물이 번져나가는 것
		for(int i=0; i<r; i++){
			for(int j=0; j<c; j++){
				if(map[i][j] == 1)
					flood_bfs(i, j);
			}
		}
		
		//바로 1로 바꾸면 배열안에 계속 들어가게됨 후에 바꿈, 물이 여러개인 경우도 고려
		for(int i=0; i<r; i++){
			for(int j=0; j<c; j++){
				if(map[i][j] == 3)
					map[i][j] = 1;
			}
		}
		
		int k=0;
		//슴도치 움직임
		//슴도치가 움직일수있는 지역을 알아냄
		for(int i=0; i<r; i++){
			for(int j=0; j<c; j++){
				if(map[i][j] == -1){
					sumdo_x[k] = i;
					sumdo_y[k] = j;
					k++;
				}
			}
		}
		//각지역마다 움직일수있는 곳으로 이동
		for(int i=0; i<k; i++){
			sumdo_bfs(sumdo_x[i], sumdo_y[i]);
		}

		//test//
		// for(int i=0; i<r; i++){
		// 	for(int j=0; j<c; j++){
		// 		printf("%d", map[i][j]);
		// 	}
		// 	printf("\n");
		// }
		// printf("\n");
		//test//
		
		//종료조건 검사
		int cond1 = 0;
		for(int i=0; i<r; i++){
			for(int j=0; j<c; j++){
				if(map[i][j] == -2)// 못도착
					cond1++; // cond1이 0이면 도착
			}
		}
		if(cond1 == 0){
			flag = 0;
		}
		
		cond_bfs(ter_x, ter_y);
		if(cond2 == 4) {// 4방향 모두 1이거나 못가는 곳포함 해서 4
			printf("KAKTUS");
			return 0;
		}
		cond2 = 0; //condition2 초기화
		result = result + 1;
	}
	
	printf("%d", result);
	
	return 0;
}

ha_ram 4년 전 0

반례입니다.

5 4

.D.*

.X..

..*.

....

S...

답 : KAKTUS

ha_ram 4년 전 0

아마 32번째 줄에 조건이 빈칸일때만 물이 번지게 되어있어서

만약 물이 번져야 할 곳에 고슴도치가 있다면 그곳에 물이 번지지 않게 되어서

틀리는것 같습니다.

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

문제

문제

출처

ICPC

탈출문제 도움부탁드립니다.

suleesulee 4년 전 0

ha_ram 4년 전 0

ha_ram 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말