글 읽기 - 10218번 Maze

shinsy11 8년 전 0

BFS 방식을 사용하여 모든 시작가능한 위치를 기점으로 BFS 함수를 사용했습니다. 시작 위치에 따라 두가지 방방법이 있을 경우 가장 긴 경우를 저장하였고 하나의 시작점에서라도 탈출구를 찾을 수 없을 경우 "XHAE"를 출력합니다.

새로운 길을 찾을 때 마다 해당 X값과 Y값, 움직인 횟 수, 그리고 방향(LRUD)을 저장해주었습니다. 중복되거나 왔던 길을 다시 되돌아 오는것을 방지하기 위해서 방문한 위치는 visited로 표시를 해주어 방문하지 않은 곳만 고려해 주었는데요.

50%까지는 채점이 되었는데 틀린답이라고 하네요.

어떤부분이 잘 못 된걸까요? 고려하지 않은 사항이 있는걸까요...?

도와주세요!

#include<iostream>
#include<vector>
#include<string>
#include<string.h>
using namespace std;

char board[10][10];
int height, width;

string bfs(int i, int j){
	int visited[10][10], pos = 0;
	vector<int> X, Y, M;
	vector<string> D;

	memset(visited, 0, sizeof(visited));

	X.push_back(j);
	Y.push_back(i);
	M.push_back(0);
	D.push_back("");
	visited[i][j] = 1;

	while(pos < X.size() && board[Y[pos]][X[pos]] != 'O' && M[pos] <= 10){
		i = Y[pos];
		j = X[pos];

		while(j-1 >= 0 && board[i][j-1] != '#' && visited[i][j-1] == 0){
			j--;
			visited[i][j] = 1;
		}
		if(j != X[pos]){
			X.push_back(j);
			Y.push_back(i);
			M.push_back(M[pos]+1);
			D.push_back(D[pos]+"L");
			j = X[pos];
		}

		while(j+1 < width && board[i][j+1] != '#' && visited[i][j+1] == 0){
			j++;
			visited[i][j] = 1;
		}
		if(j != X[pos]){
			X.push_back(j);
			Y.push_back(i);
			M.push_back(M[pos]+1);
			D.push_back(D[pos]+"R");
			j = X[pos];
		}

		while(i-1 >= 0 && board[i-1][j] != '#' && visited[i-1][j] == 0){
			i--;
			visited[i][j] = 1;
		}
		if(i != Y[pos]){
			X.push_back(j);
			Y.push_back(i);
			M.push_back(M[pos]+1);
			D.push_back(D[pos]+"U");
			i = Y[pos];
		}

		while(i+1 < height && board[i+1][j] != '#' && visited[i+1][j] == 0){
			i++;
			visited[i][j] = 1;
		}
		if(i != Y[pos]){
			X.push_back(j);
			Y.push_back(i);
			M.push_back(M[pos]+1);
			D.push_back(D[pos]+"D");
			i = Y[pos];
		}

		pos++;
	}

	if(pos >= X.size() || M[pos] > 10)
		return "fail";
	else
		return D[pos];
}

string findMaze(){
	int i, j;
	string ans, temp;

	for(i=0; i<height; i++)
		for(j=0; j<width; j++)
			if(board[i][j] == '.'){
				if(bfs(i, j) == "fail")
					return "XHAE";
				else{
					temp = bfs(i, j);
					if(ans.length() < temp.length())
						ans.assign(temp);
				}
			}
	
	return ans;
}

int main(){
	int i, j, trial;

	cin >> trial;
	while(trial--){
		cin >> height >> width;

		for(i=0; i<height; i++)
			for(j=0; j<width; j++)
				cin >> board[i][j];

		cout << findMaze() << endl;
	}

	return 0;
}

kdhsong 8년 전 0

저랑 비슷하네요 ...

저도 50퍼에서 안넘어가네요

혹시 해결하셧나요 10번틀렸습니다 흑

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

문제

문제

출처

ICPC

10218번 Maze

shinsy11 8년 전 0

kdhsong 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말