BOJ 16920 C++

코드

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;

int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
int vis[1001][1001];
int ans[10];
int player[10];

class cord
{
public:
    int x, y, num;
    cord(int _x, int _y, int _num) : x(_x), y(_y), num(_num){};
};
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, p;
    cin >> n >> m >> p;
    queue<cord> q[10];
    for (int i = 1; i <= p; i++)
    {
        cin >> player[i];
    }
    char ch;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> ch;
            if (ch == '.')
            {
                vis[i][j] = 1;
            }
            else if (ch == '#')
            {
                vis[i][j] = 0;
            }
            else
            {
                vis[i][j] = 0;
                ans[ch - '0']++;
                q[ch - '0'].push(cord(i, j, 0));
            }
        }
    }

    while (1)
    {
        bool flag = 0;

        for (int i = 1; i <= p; i++)
        {
            queue<cord> nq;
            while (!q[i].empty())
            {
                auto cur = q[i].front();
                q[i].pop();
                if (cur.num >= player[i])
                {
                    nq.push(cord(cur.x, cur.y, 0));
                    continue;
                }
                for (int dir = 0; dir < 4; dir++)
                {
                    int nx = dx[dir] + cur.x;
                    int ny = dy[dir] + cur.y;
                    if (nx >= n || nx < 0 || ny >= m || ny < 0)
                        continue;
                    if (!vis[nx][ny])
                        continue;
                    q[i].push(cord(nx, ny, cur.num + 1));
                    vis[nx][ny] = 0;
                    ans[i]++;
                    flag = 1;
                }
            }
            q[i] = nq;
        }
        if (!flag)
            break;
    }
    for (int i = 1; i <= p; i++)
    {
        cout << ans[i] << " ";
    }
    return 0;
}

설명

지문에서 Si칸을 동시에 확장한다고 하는데 이 부분을 잘못 이해했다. 이동가능한 칸이니 이동 가능한 칸이 2칸이면

.....1....  
....111...  
...11111..   <- 가운데 1 기준
....111...  
.....1....  

이런식으로 확장한다는것을 이해 하여야 풀 수 있다..