2636번

2636

#include <iostream>
#include <queue>

using namespace std;
int a, b;
int map[100][100];
bool visited[100][100] = {
    false,
};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int cheeseCnt = 0;

void bfs()
{
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));

    while (!q.empty())
    {
        pair<int, int> p = q.front();
        int x = p.first;
        int y = p.second;
        q.pop();
        visited[x][y] = true;
        for (int i = 0; i < 4; i++)
        {
            int tmpX = x + dx[i];
            int tmpY = y + dy[i];
            if (tmpX < 0 || tmpX >= a || tmpY < 0 || tmpY >= b || visited[tmpX][tmpY])
                continue;
            visited[tmpX][tmpY] = true;
            if (map[tmpX][tmpY] == 1)
            {
                map[tmpX][tmpY] = -1;
            }
            else if (map[tmpX][tmpY] == 0)
            {
                q.push(make_pair(tmpX, tmpY));
            }
        }
    }
}

void updateMapAndCalculateCheese()
{
    int tmpCheeseCnt = 0;
    int visitCheeseCnt = 0;
    for (int i = 0; i < a; i++)
    {
        for (int j = 0; j < b; j++)
        {
            if (map[i][j] == -1)
            {
                map[i][j] = 0;
                visitCheeseCnt++;
            }
            else if (map[i][j] == 1)
                tmpCheeseCnt++;
        }
    }
    if (tmpCheeseCnt != 0)
    {
        cheeseCnt = tmpCheeseCnt;
    }
    else
    {
        cheeseCnt = visitCheeseCnt;
    }
}

bool isEmptyMap()
{
    for (int i = 0; i < a; i++)
    {
        for (int j = 0; j < b; j++)
        {
            if (map[i][j] == 1)
            {
                return false;
            }
        }
    }
    return true;
}

void initVisit()
{
    for (int i = 0; i < a; i++)
    {
        for (int j = 0; j < b; j++)
        {
            visited[i][j] = false;
        }
    }
}

int main()
{
    cin >> a >> b;
    for (int i = 0; i < a; i++)
    {
        for (int j = 0; j < b; j++)
        {
            cin >> map[i][j];
        }
    }

    int time = 0;
    while (!isEmptyMap())
    {
        bfs();
        updateMapAndCalculateCheese();
        time++;
        initVisit();
    }
    cout << time << endl;
    cout << cheeseCnt << endl;
}