글 읽기 - 고수님들 도와주세요

math_rabbit_1028 4년 전 0

DFS로 짰는데 시간 초과가 나옵니다. DFS로 시간 초과가 안 나는 방법은 없나요?

//16933 - 벽 부수고 이동하기 3
#include <iostream>
using namespace std;
int n, m, k, ch[1010][1010], f = 0, res = 2147000000;
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
char map[1010][1010];
bool t = true;

void DFS(int x, int y, int L) {
	if (res < L + (n - x - 1) + (m - y - 1)) return;
	if (x == n - 1 && y == m - 1) {
		if (res > L) res = L;
	}
	else {
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i], yy = y + dy[i];
			if (0 <= xx && xx < n && 0 <= yy && yy < m && ch[xx][yy] == 0) {
				if (map[xx][yy] == '0') {
					ch[xx][yy] = 1;
					t = !t;
					DFS(xx, yy, L + 1);
					ch[xx][yy] = 0;
					t = !t;
				}
				else if (f < k) {
					ch[xx][yy] = 1;
					f++;
					if (t) {
						t = !t;
						DFS(xx, yy, L + 1);
						t = !t;
					}
					else DFS(xx, yy, L + 2);
					f--;
					ch[xx][yy] = 0;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) cin >> map[i];
	ch[0][0] = 1;
	DFS(0, 0, 1);
	if (res == 2147000000) cout << "-1\n";
	else cout << res << '\n';
	return 0;
}

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

문제

문제

출처

ICPC

고수님들 도와주세요

math_rabbit_1028 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말