글 읽기 - 반례나 틀린부분 지적 부탁드립니다

cool2684 5년 전 0

.게시판에 올라온 TC다 돌려봤는데 모두 맞게 나왔습니다. 물BFS후 고슴도치BFS돌렸고 D앞에서 물을 만났을 경우 들어갈 수 있으니깐 그부분만 따로 예외처리 해줬습니다. 반례나 틀린부분 지적 부탁드려요

#include<iostream>
#include<string>
#include<queue>
#include<cstring>
#include<tuple>

using namespace std;

int r, c;
string map[51];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int gsdc_x, gsdc_y;
bool check_g[51][51];
int min_ = 99999;

bool range(int i, int j) {
	if (i >= 0 && i < r&&j >= 0 && j < c)
		return true;
	else
		return false;
}

void next_w() { //물이차는 부분

	bool check_w[51][51];
	memset(check_w, false, sizeof(check_w));

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (check_w[i][j] == false && map[i][j] == '*') {
				for (int k = 0; k < 4; k++) {
					if (range(i + dy[k], j + dx[k]) && map[i + dy[k]][j + dx[k]] == '.') {
						map[i + dy[k]][j + dx[k]] = '*';
						check_w[i + dy[k]][j + dx[k]] = true;
					}
				}
			}
		}
	}
}

void bfs() {
	int prev_cnt = 0;
	memset(check_g, false, sizeof(check_g));
	queue<tuple<int, int, int>> q;
	q.push(make_tuple(gsdc_y, gsdc_x, 0));
	check_g[gsdc_y][gsdc_x] = true;
	next_w(); //물을 한단계 증가

	while (!q.empty()) {
		int y = get<0>(q.front());
		int x = get<1>(q.front());
		int cnt = get<2>(q.front());
		q.pop();

		if (prev_cnt < cnt) { //이전 단계의 물높이를 모두했으면 물높이 증가
			next_w();                   
		}
		prev_cnt = cnt;
		if (map[y][x] == '*') {
			for (int k = 0; k < 4; k++) { //D 바로앞에서 물을 만났을 경우는 예외처리
				if (range(y + dy[k], x + dx[k])) {
					if (map[y + dy[k]][x + dx[k]] == 'D') {
						if (min_ > cnt + 1) {
							min_ = cnt + 1;
						}
					}
				}
			}
			continue;
		}


		for (int k = 0; k < 4; k++) { //4방향으로 고슴도치 BFS
			if (range(y + dy[k], x + dx[k]) && check_g[y + dy[k]][x + dx[k]] == false) {
				if (map[y + dy[k]][x + dx[k]] == '.') {
					q.push(make_tuple(y + dy[k], x + dx[k], cnt + 1));
					check_g[y + dy[k]][x + dx[k]] = true;
				}
				else if (map[y + dy[k]][x + dx[k]] == 'D') {
					if (min_ > cnt + 1) {
						min_ = cnt + 1;
					}
				}
			}
		}
	}
}

int main() {
	
	cin >> r >> c;

	for (int i = 0; i < r; i++) {
		cin >> map[i];
	}

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (map[i][j] == 'S') {
				map[i][j] = '.';
				gsdc_x = j;
				gsdc_y = i;
			}
		}
	}
	bfs();
	if (min_ == 99999)
		cout << "KAKTUS";
	else
		cout << min_;
	return 0;
}

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

문제

문제

출처

ICPC

반례나 틀린부분 지적 부탁드립니다

cool2684 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말