백준[20208] 진우의 민트초코우유

문제 설명

문제 링크

http://icpc.me/20208

20208번: 진우의 민트초코우유

풀이

끔찍한 민트초코의 최대 개수가 10개이기 때문에 백트레킹으로 전탐색을 하면 된다.

이때 집에 다시 돌아올 수 있는것을 고려해줘야 하는데, 남은 체력보다 집까지의 거리가 더 클 때 최댓값을 갱신해주면 된다.

구현을 할때는 dfs를 하듯이 모든 점을 움직이면서 탐색한다면 나올 수 있는 경로가 매우 많아 시간이 터지고 민트초코가 있는 위치를 저장해놓은 후에 그 점들 사이에서만 움직여야 한다.

코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
using pii = pair<int, int>;

vector<pii> v;
pii start;
int n, m, h, ans;
bool visited[12];

int dist(pii a, pii b) { return abs(a.first - b.first) + abs(a.second - b.second); }

void solve(pii cur, int die, int eat) {
    if (die >= dist(cur, start)) ans = max(ans, eat);
    for (int i = 0; i < v.size(); i++)  if (!visited[i]) {
        visited[i] = true;
        if (die - dist(cur, v[i]) >= 0)
            solve(v[i], die - dist(cur, v[i]) + h, eat + 1);
        visited[i] = false;
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &h);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int inp; scanf("%d", &inp);
            if (inp == 1) start = {i, j};
            else if (inp == 2) v.push_back({i, j});
        }
    }
    solve(start, m, 0);
    printf("%d", ans);
}