글 읽기 - 반례좀 부탁드립니다..

cool2684 5년 전 0

.여러가지 다 해봐도 반례를 못찾겠습니다..ㅠㅠㅠ

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

using namespace std;

int n, m, k;
string map[1001];
bool check[1001][1001];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int min_ = 99999;

void bfs() {
	int x=0, y=0, wall=0, cnt=0;

	queue<tuple<int, int, int, int>> q; //x,y,부순 벽의 개수,이동한 칸의 개수
	q.push(make_tuple(0, 0, 0, 1)); 
	check[0][0] = true;

	while (!q.empty()) {
		x = get<0>(q.front()); //[x][y]
		y = get<1>(q.front());
		wall = get<2>(q.front()); //부순벽의 개수
		cnt = get<3>(q.front()); //이동한 칸의 개수
		q.pop();

		if (x == n - 1 && y == m - 1 && min_ > cnt) {
			min_ = cnt;
		}

		for (int i = 0; i < 4; i++) {
			if (x + dx[i] >= 0 && y + dy[i] >= 0 && x + dx[i] < n && y + dy[i] < m && check[x + dx[i]][y + dy[i]] != true) {
				if (map[x + dx[i]][y + dy[i]] == '0') { //다음칸이 벽이 아닐때
					check[x + dx[i]][y + dy[i]] = true;
					q.push(make_tuple(x + dx[i], y + dy[i], wall, cnt + 1));
				}
				else if (map[x + dx[i]][y + dy[i]] == '1' && wall < k) {//다음칸이 벽일때
					check[x + dx[i]][y + dy[i]] = true;
					q.push(make_tuple(x + dx[i], y + dy[i], wall + 1, cnt + 1));
				}
			}
		}
	}
}

int main() {
	cin >> n >> m >> k;

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

	bfs();
	if (min_ == 99999)
		cout << -1;
	else
		cout << min_;
	return 0;
}

djm03178 5년 전 1

먼저 https://www.acmicpc.net/problem/2206 이 문제를 풀어보세요. 더 쉬운 버전입니다.

그리고 https://www.acmicpc.net/board/view/27386 도 읽어보세요.

cool2684 5년 전 0

.주신링크가 많은 도움이 됐습니다 감사합니다

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

문제

문제

출처

ICPC

반례좀 부탁드립니다..

cool2684 5년 전 0

djm03178 5년 전 1

cool2684 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말