백준 2933 : 미네랄 c++

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

2933번: 미네랄

18500 : 미네랄 2와 거의 동일한 문제, 동일한 코드로 정답처리됨

18500번: 미네랄 2 (acmicpc.net)

설명
BFS를 이용한 구현문제이다.
미네랄을 하나 지우고 만약 분리가 된다면 아래로 내려갈 수 있을 때 까지 내리는 문제
bitset으로 구현하였다. 미네랄 배치를 bit로 나타내서 AND 연산 결과가 하나라도 1이 나오면 충돌한다는 의미이다.

 

1. 바닥과 붙어있는 모든 미네랄들을 새로운 cache 비트셋에 복사한다. 기존의 v에서는 0으로 만든다.
2. 해당 작업을 마치면 v에 남아있는건 따로 떨어져있는 클러스터이다.
3. v를 한줄씩 내리면서 내릴 수 있는지 확인한다. 바닥과 닿거나 다른 미네랄과 부딪히면 중단한다.
4. or 연산을 통해 다시 하나로 합친다.

 

#include<bits/stdc++.h>
#include<time.h>


#define MAX 1000000007
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dx[8] = { 0, 0, 1, -1, 0, 0, -1, -1 };
int dy[8] = { 1, -1, 0, 0, -1, -1, 0, 0 };

/*
int dx[2][6] = {
    {1, -1, 0, 0 ,1, -1},
    {1, -1, 0, 0, -1, 1}
};
int dy[2][6] = {
    {0, 0, 1, -1 ,1, -1},
    {0, 0, 1, -1, 1, -1}
};*/

//int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
//int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }

int n, m;
bitset<100> v[100];

queue<pii> q;
void func() {

    //바닥부터 올라와있는 모든 미네랄 복사
    bitset<100> cache[100];
    for (int i = 0; i < m; i++) {
        if (v[n - 1][i] == 1) {
            v[n - 1][i] = 0;
            cache[n - 1][i] = 1;
            q.push({ n - 1,i });
        }
    }

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;

            if (v[nx][ny] == 1) {
                v[nx][ny] = 0;
                cache[nx][ny] = 1;
                q.push({ nx,ny });
            }
        }
    }

    //현재 v에는 따로 떨어져있는 클러스터만 남아있음
    //해당 클러스터를 아래로 내릴 수 있는 지 체크
    int k = n;
    while (k--) {
        bool flag = true;
        if (v[n - 1].any()) {
            flag = false; break;
        }
        for (int i = n - 2; i >= 0; i--) {
            bitset<100> bs = (cache[i + 1] & v[i]);
            if (bs.any()) {
                flag = false; break;
            }
        }

        if (flag) {
            for (int i = n - 1; i >= 1; i--) {
                v[i] = v[i - 1];
            }
            v[0].reset();
        }
    }

    //다시 합치기
    for (int i = 0; i < n; i++) {
        v[i] |= cache[i];
    }
}

int main() {
    init();
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] == 'x') v[i][j] = 1;
        }
    }

    int turn; cin >> turn;
    for (int i = 0; i < turn; i++) {
        int h; cin >> h;
        int d = (i % 2 == 0 ? 1 : -1);
        int s = (i % 2 == 0 ? 0 : m - 1);

        for (int i = s; i < m && i >= 0; i += d) {
            if (v[n - h][i] == 1) {
                v[n - h][i] = 0;
                break;
            }
        }

        func();
    }

    //출력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << (v[i][j] == 0 ? '.' : 'x');
        }
        cout << "\n";
    }
}