백준 16197 / 두 동전

구슬 탈출2 문제(https://naivep.tistory.com/25)와 해법은 같다.

총 버튼을 10번 누를 수 있으니 

오른쪽 왼쪽 위 아래 4 버튼을 10번씩 누를 수 있는 모든 경우의 수를 구한다.

4^10은 100만정도되니 시간초과에 걸리지 않는다.

동전을 움직이기 전, 맵의 가장자리를 모두 x로 채운다. (나간 경우를 처리하기 위해)

구한 경우의 수 마다 동전을 움직여서

그 턴에 빠진 개수를 구한다.

빠진 개수가 1이면 몇번쨰 누르는 버튼인지 리턴하고,

빠진 개수가 2이면 9999를 리턴한다. (9999는 경우를 무시하기 위해 임의로 설정해놓은 수)

10번을 다 눌렀는데 두 개의 코인이 모두 맵 안에 있어도 9999를 리턴한다.

코드

#include<stdio.h>
#include<queue>
#include<iostream>
#include<vector>
#include<memory.h>
 
using namespace std;
 
int n, m;
 
char map[22][22];
int tmpdir[10];
 
vector<pair<int, int>>coin;
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
queue<pair<int, int>>q;
int minn = 1000;
 
int go() {
 
    while (!q.empty()) {
        q.pop();
    }
 
    int x = coin[0].first;
    int y = coin[0].second;
    int xx = coin[1].first;
    int yy = coin[1].second;
 
    int out = 0;
 
    for (int i = 0; i < 10; i++) {
        int dir = tmpdir[i];
 
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        int nxx = xx + dx[dir];
        int nyy = yy + dy[dir];
 
        if (map[nx][ny] == '.' || map[nx][ny]=='o') {
            x = nx; y = ny;
        }
        if (map[nxx][nyy] == '.' || map[nxx][nyy] == 'o') {
            xx = nxx; yy = nyy;
        }
        if (map[nx][ny] == 'x') {
            out++;
        }
        if (map[nxx][nyy] == 'x') {
            out++;
        }
    
        if (out == 1) {
            return i + 1;
        }
        if (out == 2) {
            return 9999;
        }
    }
    return 9999;
}
void makedir(int idx) {
    if (idx == 10) {
        
        int ans = go();
 
        if (ans != 9999) {
            if (minn > ans) {
                minn = ans;
            }
        }
        return;
    }
    for (int i = 0; i < 4; i++) {
        tmpdir[idx] = i;
        makedir(idx+1);
    }
}
 
int main() {
    //freopen("Text.txt", "r", stdin);
 
    memset(map, 'x', sizeof(map));
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'o') {
                coin.push_back({ i,j });
            }
        }
    }
    makedir(0);
 
    if (minn != 1000) {
        cout << minn << endl;
    }
    else {
        cout << -1 << endl;
    }
 
}