A8037.腐烂的橘子

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

在给定的 n×mn \times m 网格中,每个单元格可以有以下三个值之一:

  1. 00 代表空单元格;
  2. 11 代表新鲜橘子;
  3. 22 代表腐烂的橘子。

每分钟,腐烂的橘子周围 44 个方向上相邻的新鲜橘子都会腐烂。

需要求出直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,输出 1-1

输入格式

第一行两个整数 n,m(1n,m1000)n,m(1 \leq n,m \leq 1000),表示网格的行数和列数。

接下来 nn 行,每行 mm 个数。

输出格式

输出直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,输出 1-1

输入输出样例

  • 输入#1

    3 3
    2 1 1
    1 1 0
    0 1 1

    输出#1

    4
  • 输入#2

    3 3
    2 1 1
    0 1 1
    1 0 1

    输出#2

    -1
  • 输入#3

    1 2
    0 2

    输出#3

    0

【普及组算法9】广度优先搜索

0/20
首页