白駿アルゴリズム7576号:トマト(2次元)

リンク

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

質問する

チョルスのトマト農場にはトマトを保管する大きな倉庫がある.トマトは下図のように1つずつ四角い格子に入れて倉庫に保管しています.

倉庫に保管されているトマトの中には、熟しているものもあれば、まだ熟していないものもあります.1日保管した後、熟したトマトに隣接する未熟のトマトは、熟したトマトの影響を受けて成熟する.1つのトマトの隣接する場所は、左、右、前、後の4つの方向に位置するトマトを意味する.対角線方向に影響を与えないトマトは、トマトが自分で成熟しないと仮定します.哲洙は倉庫に保管されているトマトが何日で熟れるか、最低日数を知りたいと思っている.
倉庫にトマトのチェックボックスの大きさ、熟したトマトと未熟なトマトの情報を保管している場合、数日後には、トマトが熟しているかどうか、最低日数を求めるプログラムを作成します.しかし、箱のいくつかの格にはトマトが入っていないかもしれません.

入力

最初の行は、ボックスのサイズを表す2つの整数M,Nを与える.Mは箱の横格子数,Nは箱の縦格子数を表す.しかし,2≦M,N≦1000であった.2行目から、1つの箱に保存されているトマトの情報が提供されます.つまり、2行目からN行目まで、箱の中のトマトの情報が出てきます.1本の線上で、箱の横線のトマトの状態はM個の整数である.整数1は熟したトマトを表し、整数0は未熟のトマトを表し、整数-1はトマトを含まない格子を表す.
トマトが1つ以上ある場合にのみ入力します.

しゅつりょく

トマトがすべて熟成した最小日付を印刷します.保存からすべてのトマトが熟成している場合は0を、トマトが熟成していない場合は-1を出力します.

入力と出力の例

解法

1.質問で求める最小日付は、最初の始点からトマトを熟成して最後の終点までの距離を求めることに等しい
2.距離を求める問題なのでBFSを使う
3.距離を表すdist配列が0に初期化されているため、boardに値を入力したときに成熟したトマトがある場合(board[i][j]=1の場合)、それをキューに入れてBFSを起動し、board値が0の場合、dist配列はその座標値を-1に設定する(dist配列が0に初期化されるため).
4.一般的なBFSの実行時に距離を求め、distの値が-1でない場合はスキップする.(熟していないトマトではないので)
5.重なった複文を回して、未熟なトマトがあるかどうかを確認し、答えを印刷します.

プールコード（C++）

// 7576번 : 토마토(실버 1)

#include <iostream>
#include <queue>
#include <algorithm>
#include <math.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX 1000
using namespace std;

int board[MAX][MAX] = {
    0,
};
int dist[MAX][MAX] = {0, 0};
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    int m, n; // m : 가로칸 수, n : 세로 칸 수
    fastio;
    queue<pair<int, int>> q;
    cin >> m >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 1)
            {
                q.push(make_pair(i, j));
            }
            if (board[i][j] == 0)
            {
                dist[i][j] = -1;
            }
        }
    }
    while (!q.empty())
    {
        auto cur = q.front(); // 현재 큐에 있는 좌표 pair값
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int newX = cur.first + dx[i];
            int newY = cur.second + dy[i];
            if (0 > newX || newX >= n || 0 > newY || newY >= m)
                continue;
            if (dist[newX][newY] != -1)
                continue;
            q.push(make_pair(newX, newY));
            dist[newX][newY] = dist[cur.first][cur.second] + 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (dist[i][j] == -1)
            {
                cout << "-1";
                return 0;
            }
            ans = max(ans, dist[i][j]);
        }
    }
    cout << ans;
    return 0;
}