글 읽기 - BFS로 풀었는데 틀린케이스를 잘 모르겠습니다.

bsdlcksdn 7년 전 0

BFS로 1칸씩 전진해가는걸 나타내려고 기존 배열을 char로 받지 않고 int형으로 변환시켰습니다.

기존 초기화는 -10으로 해놨고.

ex) 고슴도치=>0, 물=-2, 동굴=-3, 돌=-4, 이동가능자리=-5 이런식으로 했습니다.

queue에 삽입해서 돌리다가, 동굴만나면 탈출하는 방식으로 flag를 걸었는데 틀렸다고 출력이나옵니다.

질문검색에 틀리신 케이스들 돌려봐도 잘 나오는데,, 어디서 틀린건지 잘 모르겠습니다.

#include <iostream>
using namespace std;

int n, m;
int board[60][60];
int check[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };


int h = 0, r = 0;
int queue[10000000];

void enqueue(int a) {
	queue[r++] = a;
}

int dequeue() {
	return queue[h++];
}


int main() {


	//초기화
	for (int i = 0; i < 60; i++) {
		for (int j = 0; j < 60; j++) {
			board[i][j] = -10;
		}
	}

	//입력
	cin >> n >> m;

	int w_x=0, w_y=0;
	int a_x=0, a_y=0;
	int d_x = 0, d_y = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {

			char temp;

			cin >> temp;

			//고슴도치. = 0;
			if (temp == 'S') {
				a_x = i;
				a_y = j;
				board[i][j] = 0;
			}
			//water
			else if (temp == '*') {
				w_x = i;
				w_y = j;
				board[i][j] = -2;
			}
			//동굴
			else if (temp == 'D') {
				d_x = i;
				d_y = j;
				board[i][j] = -3;
			}

			//돌
			else if (temp == 'X') {
				board[i][j] = -4;
			}

			//땅
			else if (temp == '.') {
				board[i][j] = -5;
			}
		}
	}

	//enqueue_water
	enqueue((w_x)* 100 + w_y);
	//enqueue_animal
	enqueue((a_x)* 100 + a_y);


	//BFS
	bool stop = false;

	while (h != r) {

		//검사
		cout << "test" <<endl;
		for (int i = 0; i < n+2; i++) {
			for (int j = 0; j < m+2; j++) {
				cout << board[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;

		
		int temp = dequeue();
		int x = temp / 100;
		int y = temp % 100;

		for (int i = 0; i < 4; i++) {
			int a = x + check[i][0];
			int b = y + check[i][1];

			//water
			if (board[x][y] == -2 && board[a][b] == -5) {
				enqueue((a * 100) + b);
				board[a][b] = -2;
			}

			//stop
			if (board[x][y] >= 0 && board[a][b] == -3) {
				board[a][b] = board[x][y] + 1;
				stop = true;
				break;
			}

			//animal
			else if (board[x][y] >= 0 && board[a][b] == -5) {

				enqueue((a * 100) + b);
				board[a][b] = board[x][y]+1;
			}
		}
		if (stop) {
			break;
		}
		
		

	}

	if (stop) {
		cout << board[d_x][d_y] << endl;
	}
	else {
		cout << "KAKTUS" << endl;
	}	


}

portableangel 7년 전 0

초기 상태에서 물(*)이 한 칸에만 있다는 보장이 없지 않나요?

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

문제

문제

출처

ICPC

BFS로 풀었는데 틀린케이스를 잘 모르겠습니다.

bsdlcksdn 7년 전 0

portableangel 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말