题目描述

公司的程序员不够用了，决定把产品经理都转变为程序员以解决开发时间长的问题。

在给定的矩形网格中，每个单元格可以有以下三个值之一：

值 0 代表空单元格;
值 1 代表产品经理;
值 2 代表程序员;
每分钟，任何与程序员(在 4 个正方向上)相邻的产品经理都会变成程序员。

返回直到单元格中没有产品经理为止所必须经过的最小分钟数。

如果不可能，返回 −1。

以下是一个 4 分钟转变完成的示例：

2 1 1      2 2 1      2 2 2      2 2 2      2 2 2
1 1 0  ->  2 1 0  ->  2 2 0  ->  2 2 0  ->  2 2 0
0 1 1      0 1 1      0 1 1      0 2 1      0 2 2

输入格式
不固定多行（行数不超过 10），毎行是按照空格分割的数字(不固定，毎行数字个数不超过 10)。

其中每个数组项的取值仅为 0、1、2 三种。

读取时可以按行读取，直到读取到空行为止，再对读取的所有行做转换处理。

输出格式
如果能够将所有产品经理变成程序员，则输出最小的分钟数。

如果不能够将所有的产品经理变成程序员，则返回 −1。

输入样例1：
0 2
1 0
输出样例1：
-1
输入样例2：
1 2 1
1 1 0
0 1 1
输出样例2：
3
输入样例3：
1 2
2 1
1 2
0 1
0 1
1 1
输出样例3：
4

解法如下：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static Scanner sc=new Scanner(System.in);

    static int N=15;
    static String srr[][]=new String[N][N];

    static int a[][]=new int[N][N];

    static int d[][]=new int[N][N];    //记录“感染”到当前格子所用的时间

    static int dx[]=new int[] {-1,1,0,0};
    static int dy[]=new int[] {0,0,-1,1};


    public static class Node{

        int x;
        int y;

        public Node(int x,int y) {
            this.x=x;
            this.y=y;

        }
    }


    public static void main(String[] args) {

        int len=0;

        while(sc.hasNextLine()) {

            len++;
            srr[len]=sc.nextLine().split(" ");   //srr数组的第二维下标是从0开始的，而a数组的第二维下标是从1开始的

        }

        int n=len;                //矩形网格行数
        int m=srr[1].length;      //矩形网格列数

        Queue<Node> q=new LinkedList<Node>();


        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                a[i][j]=Integer.parseInt(srr[i][j-1]);  //这里srr的第二维要减去1，因为srr数组的第二维下标是从0开始的，而a数组的第二维下标是从1开始的

                if(a[i][j]==2) {
                    q.offer(new Node(i,j));    //注意可能有多个源点嗷
                }
            }
        }


        while(!q.isEmpty()) {

            Node anode=q.poll();

            for(int i=0;i<4;i++) {

                int xi=anode.x+dx[i];
                int yi=anode.y+dy[i];

                if(xi>=1&&xi<=n&&yi>=1&&yi<=m&&a[xi][yi]==1) {

                    q.offer(new Node(xi,yi));
                    a[xi][yi]=2;     //入队的时候就要立刻进行标记！
                    d[xi][yi]=d[anode.x][anode.y]+1;
                }
            }

        }


        int ans=0;

        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {

                ans=Math.max(ans, d[i][j]);

                if(a[i][j]==1) {       //如果此时矩形网格中还有1，则说明无解
                    System.out.println(-1);
                    System.exit(0);
                }
            }
        }

        System.out.println(ans);
    }



}