구슬 탈출 2 (중요!!)

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

13460번: 구슬 탈출 2

 

1. 10번 이하로 움직여서 꺼낼 수 없으면 -1 출력 

10보다 커지면 return하면 되겠다.

 

2. 경우의 수 카운트

같은 방향으로 연속해서 두 번 이동은 의미가 없다.

한 방향으로 이동한 다음, 반대 방향으로 가는 것도 의미가 없다. 

이동을 카운트 할 때, 이렇게 씹히는 걸 고려하면

시간이 매우 줄어든다.

애당초 그걸 노리고 낸 문제들이다.

 

4 × 2 ^ 9 = 2,048 가지가 나온다.

 

8 퍼즐 문제를 떠올려보면

배열을 복사하면서 경우의 수 다 따라가면

절대로 불가능 하다는 것을 안다.

 

 

 

 

비트마스크로 경우의 수를 표현해야한다.

길이가 10인

4진법 수로 표현을 한다!

 

 

<소스 코드>

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
int LIMIT = 10;
 
vector<int> gen(int k)
{
    vector<int> a(LIMIT);
    for (int i = 0; i < LIMIT; i++)
    {
        a[i] = (k & 3);
        k >>= 2;
        // a[i] = k % 4;
        // k /= 4;
    }
    return a;
}
 
// k는 방향, x와 y에 빨간 구슬이나 파란 구슬이 들어옴
pair<bool, bool> simulate(vector<string>& a, int k, int& x, int& y)
{
    if (a[x][y] == '.')
        return make_pair(false, false);
    // 행
    int n = a.size();
    // 열
    int m = a[0].size();
    bool moved = false;
    while (true)
    {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m)
        {
            return make_pair(moved, false);
        }
 
        if (a[nx][ny] == '#')
        {
            return make_pair(moved, false);
        }
        else if (a[nx][ny] == 'R' || a[nx][ny] == 'B')
        {
            return make_pair(moved, false);
        }
        // 빈 공간
        else if (a[nx][ny] == '.')
        {
            swap(a[nx][ny], a[x][y]);
            x = nx;
            y = ny;
            moved = true;
        }
        else if (a[nx][ny] == 'O')
        {
            a[x][y] = '.';
            moved = true;
            return make_pair(moved, true);
        }
    }
    return make_pair(false, false);
}
 
int check(vector<string> a, vector<int>& dir)
{
    // 행
    int n = a.size();
    // 열
    int m = a[0].size();
 
    // 구멍, 빨간 구슬, 파란 구슬
    int hx, hy, rx, ry, bx, by;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (a[i][j] == 'O')
            {
                hx = i; hy = j;
            }
            else if (a[i][j] == 'R')
            {
                rx = i; ry = j;
            }
            else if (a[i][j] == 'B')
            {
                bx = i; by = j;
            }
        }
    }
 
    int cnt = 0;
    for (int k : dir)
    {
        cnt += 1;
        bool hole1 = false, hole2 = false;
        while (true)
        {
            // 빨간 공 simulation
            auto p1 = simulate(a, k, rx, ry);
            // 파란 공 simulation
            auto p2 = simulate(a, k, bx, by);
            // 공들이 더 이상 이동 불가능
            if (p1.first == false && p2.first == false)
            {
                break;
            }
 
            if (p1.second)
                hole1 = true;
            if (p2.second)
                hole2 = true;
        }
        // 파란 공이 들어가면 무조건 실패
        if (hole2)
            return -1;
        if (hole1)
            return cnt;
    }
    return -1;
}
 
// 필요없는 경우의 수 제거
bool valid(vector<int>& dir)
{
    // 0 ~ 9까지
    for (int i = 0; i < dir.size() - 1; i++)
    {
        // 왕복
        if (dir[i] == 0 && dir[i + 1] == 1)
            return false;
        if (dir[i] == 1 && dir[i + 1] == 0)
            return false;
        if (dir[i] == 2 && dir[i + 1] == 3)
            return false;
        if (dir[i] == 3 && dir[i + 1] == 2)
            return false;
        // 씹힘
        if (dir[i] == dir[i + 1])
            return false;
    }
    return true;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
 
    int ans = -1;
 
    // 2 ^ 20 = 4 ^ 10
    for (int k = 0; k < (1 << (LIMIT * 2)); k++)
    {
        // 4진법으로 표현된 방향이 들어간다.
        vector<int> dir = gen(k);
 
        // 필요없는 경우의 수면 continue
        if (!valid(dir))
            continue;
 
        int cur = check(a, dir);
        // 파란 공이 들어감 continue
        if (cur == -1)
            continue;
 
        // ans == -1인거는 아직 초기화가 안된 것
        // 아니면 최소값을 바꿔준다.
        if (ans == -1 || ans > cur)
            ans = cur;
    }
    cout << ans << '\n';
    return 0;
}
 

 

ㅅㅂ.. m 대신 n 썼다가 이렇게 됐다

제발 제발 제발 쓸 때 확인하자