글 읽기 - 60퍼센트에서 틀렸다고 나옵니다..!

pwr2011 4년 전 0

다른 질문들의 테스트케이스는 다 맞는데 안되네요.

제가 계속 이런 비슷한 유형의 bfs를 풀고있는데 다 틀리고있습니다. 뭔가 하나의 예외를 모든 문제들마다 놓치고 있는것같은데요 한번만 봐주시면 감사하겠습니다.

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

bool visited[52][52];
int s_x, s_y;
int R, C;
pair<int, int> water[52];
int water_cnt;
char map[52][52];

int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

void bfs() { //물의 bfs 한후 고슴도치 bfs를 한다
	queue<pair<int, int>> w; 
	queue<pair<int, int>> goseum;
	int level = 0;
	for (int t = 0; t < water_cnt; t++) { //물의 위치가 여러개일수 있으니 큐에 다 넣어준다
		w.push(make_pair(water[t].first, water[t].second));
	}
	goseum.push(make_pair(s_y, s_x)); //고슴도치의 위치또한 큐에 넣어준다

	while (!goseum.empty()) { 
		int gsize = goseum.size();
		int wsize = w.size();

		for (int i = 0; i < wsize; i++) {
			int c_y = w.front().first;
			int c_x = w.front().second;
			w.pop();
			for (int d = 0; d < 4; d++) {
				int n_x = c_x + dx[d];
				int n_y = c_y + dy[d];
				if (n_x<0 || n_y < 0 || n_x>C - 1 || n_y >R - 1) continue;
				if (map[n_y][n_x] == '.' || map[n_y][n_x] == 'S') { 
					map[n_y][n_x] = '*';
					w.push(make_pair(n_y, n_x));
				}
			}
		}//물이 한 턴마다 넘치는 모습을 map에 기록한다

		for (int i = 0; i < gsize; i++) {
			int c_y = goseum.front().first;
			int c_x = goseum.front().second;
			goseum.pop();
			for (int d = 0; d < 4; d++) {
				int n_x = c_x + dx[d];
				int n_y = c_y + dy[d];
				if (n_x<0 || n_y < 0 || n_x>C - 1 || n_y >R - 1) continue;
				if (visited[n_y][n_x] == true) continue;//고슴도치는 한번 방문한곳 또 안들린다
				if (map[n_y][n_x] == 'D') { //D에 도착하면 끝
					cout << level + 1;
					return;
				}
				if (map[n_y][n_x] == '.') {
					visited[n_y][n_x] = true;
					goseum.push(make_pair(n_y, n_x));
				}
			}
		}

		level++;
	}
	cout << "KAKTUS";
	return;
}

int main()
{
	cin >> R >> C; //y x

	for (int r = 0; r < R; r++) { //입력
		string s;
		cin >> s;
		for (int c = 0; c < C; c++) {
			if (s[c] == 'S') {
				s_x = c;
				s_y = r;
				visited[s_y][s_x] = true;
			}
			if (s[c] == '*') {
				water[water_cnt].first = r;
				water[water_cnt++].second = c;
			}
			map[r][c] = s[c];
		}
	}
	bfs();

}

pwr2011 4년 전 1

10번째 줄 pair water[52]; 를 pair water[52*52];로 고치니까 해결됬습니다..... 진짜 이것때문에 몇시간을 ....

60%에서 오답나오신 분들은 아마 small test case에서는 클리어인데 사이즈가 커진 case에서 배열의 크기라던가 그런부분들을 확인해 보시는게 좋을것 같네요 화이팅!

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

문제

문제

출처

ICPC

60퍼센트에서 틀렸다고 나옵니다..!

pwr2011 4년 전 0

pwr2011 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말