[16197] 두 동전

https://www.acmicpc.net/problem/16197

16197번: 두 동전

<문제>

2개의 동전을 상하좌우로 움직이고, 동전이 한개만 맵을 벗어나게 하기 위한 움직임의 최소 횟수를 구해야한다.

동전은 겹칠 수 있지만, 이경우에는 정답의 가능성이 없다.

dfs로 구현할때에

1. depth가 10에 도달한 경우

2. 이미 구한 최적해보다 depth가 커 정답의 가능성이 없는 경우

3. 두개의 동전이 모두 맵을 벗어난 경우

위 3가지일때에는 최적해 업데이트 없이 return 해주었다.

그 밖에는 벽이 있는 4방향 dfs와 차이점이 없다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
char a[22][22];
int n, m, dy[4] = { 0, 1, 0, -1 }, dx[4] = { 1, 0, -1, 0 };
int answer = INT_MAX;
queue<pair<int, int>> q;
vector<pair<int, int>> v;
typedef struct {
    int y, x, y2, x2;
} state;
bool isCoinOut(int y, int x) {
    if (y < 0 || x < 0 || y >= n || x >= m)return true;
    return false;
}
void f(int depth, state cur) {
    int i;
    if (depth > 10)return;
    if (depth >= answer)return;
    if (isCoinOut(cur.y, cur.x) == true && isCoinOut(cur.y2, cur.x2) == true)return;
 
    if (isCoinOut(cur.y, cur.x) != isCoinOut(cur.y2, cur.x2)) {
        answer = min(depth, answer);
        return;
    }
 
    for (i = 0; i < 4; i++) {
        state next = { cur.y + dy[i], cur.x + dx[i], cur.y2 + dy[i], cur.x2 + dx[i] };
        if (a[next.y][next.x] == '#') {
            next.y = cur.y;
            next.x = cur.x;
        }
        if (a[next.y2][next.x2] == '#') {
            next.y2 = cur.y2;
            next.x2 = cur.x2;
        }
        f(depth + 1, next);
    }
}
int main(void) {
    int i, j;
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        scanf("%s", a[i]);
        for (j = 0; j < m; j++) {
            if (a[i][j] == 'o') {
                v.push_back({ i, j });
            }
        }
    }
    int _a = v[0].first, _b = v[0].second, _c = v[1].first, _d = v[1].second;
    f(0, { _a, _b, _c, _d });
    if (answer != INT_MAX)printf("%d", answer);
    else printf("-1");
    return 0;
}