# 2293 미네랄

```cpp
#include"2933.h"
using namespace std;
typedef vector<vector<char>> vvc;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

int R, C, N;
vector<int> h;
vvc cave;
vvi visited;
pii dirArr[4] = {{-1,0},{0,1},{1,0},{0,-1}};

void Output()
{
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            cout << cave[i][j];
        }
        cout << '\n';
    }
}

void Fall(int visit_flag, int fall_length)
{
    // 맨 아래 다음 행부터 훑으면서 visit_flag면 fall_length만큼 내리기
    for (int i = R-2; i > -1; i--)
    {
        for (int j = 0; j < C; j++)
        {
            if (visited[i][j] == visit_flag)
            {
                cave[i][j] = '.';
                cave[i+fall_length][j] = 'x';
            }
        }
    }
}

int GetFallLength(int visit_flag)
{
    int fall_length = 101;
    for (int j = 0; j < C; j++)
    {
        int temp = -1;
        for (int i = 0; i < R; i++)
        {
            // visit_flag를 만나면 temp를 초기화 (만나지 않은 건 -1)
            // visit_flag가 아닌데 temp가 초기화돼있다면 temp+1 처리.
            // temp가 0보다 크고 fall_length보다 작으면 fall_length 업뎃.
            if (visited[i][j] == visit_flag) temp = 0;
            else if (temp > -1)
            {
                temp++;
                if((i+1 >= R || (cave[i+1][j]=='x'&&visited[i+1][j]!=visit_flag))
                    && fall_length > temp)
                    fall_length = temp;
            }
            // 현재 문제 : 자기 안에서 벌어지는 1칸짜리 오인 낙하
        }
    }
    return fall_length;
}

bool isValid(int i, int j)
{
    if (0 <= i && i < R && 0 <= j && j < C
        && cave[i][j] == 'x')
    {
        return true;
    }
    else return false;
}

// 던지는 방향을 visit_flag로써 사용한다
bool isGrounded(int target, int count, int dir_idx)
{
    int visit_flag = 4 * count + dir_idx;
    bool grounded = false;

    // bfs 했는데 땅을 만나면 true, 못 만나면 false
    queue<pii> q;
    pii dir = dirArr[dir_idx];
    pii cp = { h[count] + dir.first,target + dir.second}; // check point
    // 만약 확인하는 곳이 범위를 벗어난다면 true 반환하여 그냥 지나가도록
    if (!isValid(cp.first, cp.second)) return true;
    // 이미 다른 클러스터와 연결돼있었다면 grounded 취급하고 반환
    if (4 * count <= visited[cp.first][cp.second]) return true;
    visited[cp.first][cp.second] = visit_flag;
    q.push(cp);
    while (!q.empty())
    {
        pii ij = q.front(); q.pop();

        if (ij.first == R-1) grounded = true;

        for (int i = 0; i < 4; i++)
        {
            int newi = ij.first + dirArr[i].first;
            int newj = ij.second + dirArr[i].second;
            if (isValid(newi, newj)
                && visited[newi][newj] != visit_flag)
            {
                q.push({ newi,newj });
                visited[newi][newj] = visit_flag;
            }
        }
    }

    if (grounded) return true;
    else return false;
}

void Simulate(int count)
{
    bool leftOrRight = count % 2;
    int target = -1;
    if (leftOrRight == 0)
        for (int j = 0; j < C; j++)
            if (cave[h[count]][j] == 'x')
            { 
                cave[h[count]][j] = '.';
                target = j; 
                break; 
            }
    if (leftOrRight == 1)
        for (int j = C - 1; -1 < j; j--)
            if (cave[h[count]][j] == 'x')
            { 
                cave[h[count]][j] = '.';
                target = j; 
                break; 
            }

    for (int i = 0; i < 4; i++)
        if (!isGrounded(target, count, i))
        {
            Fall(4 * count+i, GetFallLength(4 * count + i));
            break;
        }
}

void Input()
{
    cin >> R >> C;
    cave = vvc(R, vector<char>(C));
    visited = vvi(R, vector<int>(C, -1));

    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++)
            cin >> cave[i][j];

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int temp;
        cin >> temp;
        h.push_back(R-temp);
    }
}

void B2933::Solution()
{
    Input();
    for (int i = 0; i < N; i++) Simulate(i);
    Output();
}
```

사람을 질리게 만드는 악랄한 문제 자력으로 맞추긴 했다

```cpp
void gravity(){
    bfs(); // 바닥 클러스터 마킹

    vector<pair<int,int>> cluster;
    for(int y=0;y<r;y++){
        for(int x=0;x<c;x++){
            if(board[y][x]=='x' && !vis[y][x]) 
                cluster.push_back({y,x}); // 공중 클러스터 수집
        }
    }

    if(cluster.empty()) return;

    // 현재 위치에서 삭제
    for(auto &pos:cluster) board[pos.Y][pos.X] = '.';

    // 떨어질 수 있는 거리 계산
    int dis = 105;
    for(auto &pos:cluster){
        int ny = pos.Y+1;
        while(ny<r && board[ny][pos.X]=='.') ny++;
        dis = min(dis, ny - pos.Y - 1); // 막히기 전까지 거리
    }

    // 아래로 dis만큼 떨어뜨리기
    for(auto &pos:cluster){
        board[pos.Y + dis][pos.X] = 'x';
    }
}
```

다른 사람 풀이는 더 효율적이길래 봤더니

* 바닥에 있는 클러스터만 마킹하면 됐다
* 메모리는 1만개니까 마음껏 사용해도 돼서 visited 배열 아낄 필요도 없었다
* 체크가 안된 놈들이 공중 클러스터고, 바닥 클러스터에 대해 빔 쏴서 거리 확인하면 됐다


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined-1/2293.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.