글 읽기 - 3055 탈출문제 도와주십시오..

luckoo1 5년 전 0

예제는 다 맞습니다... 틀린예가 있을거같은데 계속 해매고있습니다..

도와주십시오...

제가 생각한 알고리즘

1.물이 차는 루트 BFS구현

2. 고슴도치가 이동하기전에 물이 차는 루트에서 물이 한칸 이동한곳 즉 배열값이 1인곳에 체크배열에 true처리해서 1로 못가게합니다.

3. 그다음에는 고슴도치가 2로 이동못하게 체크배열에 true처리합니다.

이런식으로 했습니다. 고수님들 도와주세요...

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
using namespace std;
queue < pair <int, int> > q;
char map[51][51];
int water[51][51];
int dist[51][51];
bool check[51][51];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int main() {
	int n, m;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf(" %c", &map[i][j]);
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == '*') {
				q.push(make_pair(i, j));
				check[i][j] = true;
			}
			if (map[i][j] == 'X' || map[i][j] == 'D') {
				check[i][j] = true;
			}
		}
	}                         

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		check[x][y] = true;
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
				if (check[nx][ny] == false) {
					q.push(make_pair(nx, ny));
					check[nx][ny] = true;
					water[nx][ny] = water[x][y] + 1;
				}
			}
		}
	}
	                                           /////물이 가는 루트에 대한 BFS
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			check[i][j] = false;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 'S') {
				q.push(make_pair(i, j));
				check[i][j] = true;
			}
			if (map[i][j] == 'X' || map[i][j] == '*') {
				check[i][j] = true;
			}
		}
	}
	int taboo = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		check[x][y] = true;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (water[i][j] == taboo) {
					check[i][j] = true;
				}
			}
		}
		taboo += 1;                                     //이러한 방식으로 고슴도치의 이동을 제한
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
				if (check[nx][ny] == false) {
					q.push(make_pair(nx, ny));
					check[nx][ny] = true;
					dist[nx][ny] = dist[x][y] + 1;
				}
			}
		}                                                      //고슴도치 루트에 대한 BFS
	}

	int sx;
	int sy;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 'D') {
				sx = i;
				sy = j;
			}
		}
	}
	if (dist[sx][sy] == 0) {
		printf("KAKTUS\n");
	}
	else {
		printf("%d\n", dist[sx][sy]);
	}

	return 0;
}

seico75 5년 전 1

이미 문제는 푸신 것으로 알고 있지만, 이 코드의 문제에 대해서 아직도 고민을 하실까봐 글을 남깁니다.

제가 보기에는 74~81 라인이 매번 큐에서 꺼낼때 마다 도는 것이 문제로 보입니다.

taboo += 1; 이것은 고슴도치가 한번 움직일때 마다 돌아야 하는데, 처음에는 초기위치 하나가 들어가 있지만,

두번째 턴에는 최대 4가지 가능성이 들어가 있고 세번째 턴에는 최대 16가지 가능성이 들어갈 수 있으니

실제로는 탈출할 수 있어도 이 코드에서는 나갈 수 없다고 할 수 있을 것 같습니다.

보통은 이런 경우

while( !q.empty())

{

int end = q.size();

....

taboo++;

for( int i = 0; i < end; i++

{ q.pop(); .... }

}

이렇게 다시 돌때 q 크기를 알아서 그 만큼만 돌면 그게 한 턴이니까 처리하고 또 돌고... 이렇게 많이들 하시는 것 같습니다.

혹은 턴이 끝났다는 메세지는 q에 넣는 것도 봤던 것 같습니다.

luckoo1 5년 전 0

감사합니다... 제가 부족했네요!!

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

문제

문제

출처

ICPC

3055 탈출문제 도와주십시오..

luckoo1 5년 전 0

seico75 5년 전 1

luckoo1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말