题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

java 代码

/*
多源bfs问题
多源点bfs。
从所有的源点出发，往外感染即可。
*/
import java.util.*;
import java.io.*;
public class Main {
    /**
     * @param grid: a boolean 2D matrix
     * @return: an integer
     */

    public static int KONGGE=0;
    public static int JINLI=1;
    public static int PRO=2;

    public static int[] deltaX = {1, 0, 0, -1};
    public static int[] deltaY = {0, 1, -1, 0};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        int row=0;
        int col=0;
        int[][] grid=new int[10][10];
        while((line=br.readLine())!=null){
            String[] str=line.split(" ");
            col=str.length;
            for(int i=0;i<col;i++){
                grid[row][i]=Integer.parseInt(str[i]);
            }
            row++;
        }
        System.out.println(zombie(grid));
    }
    public static int zombie(int[][] grid) {
        // write your code here
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int m=grid.length;
        int n=grid[0].length;

        int people=0;
        Queue<Coordinate> queue=new LinkedList<>();
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(grid[i][j]==JINLI){
                    people++;
                }else if(grid[i][j]==PRO){
                    queue.offer(new Coordinate(i,j));
                }
            }
        }

        if(JINLI==0){
            return 0;
        }

        //bfs
        int days=0;
        while(!queue.isEmpty()){
            days++;
            int size=queue.size();
            for(int i=0;i<size;++i){
                Coordinate zb=queue.poll();
                for(int direction=0;direction<4;++direction){
                    Coordinate adj=new Coordinate(
                        zb.x+deltaX[direction],
                        zb.y+deltaY[direction]
                    );
                    if(!isPeople(adj,grid)){
                        continue;
                    }

                    grid[adj.x][adj.y]=PRO;
                    people--;
                    if(people==0){
                        return days;
                    }
                    queue.offer(adj);
                }   
            }
        }
        return -1;

    }

    private static boolean isPeople(Coordinate coor,int[][] grid){
        int n = grid.length;
        int m = grid[0].length;

        if (coor.x < 0 || coor.x >= n) {
            return false;
        }
        if (coor.y < 0 || coor.y >= m) {
            return false;
        }
        return (grid[coor.x][coor.y] == JINLI);
    }
}

class Coordinate{
    int x,y;
    public Coordinate(int x,int y){
        this.x=x;
        this.y=y;
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla