AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

僵尸矩阵

作者: 作者的头像   爱高级的松 ,  2019-07-28 10:26:33 ,  所有人可见 ,  阅读 1366


2


题目

给一个二维网格,每一个格子都有一个值,2 代表墙,1 代表僵尸,0 代表人类(数字 0, 1, 2)。僵尸每天可以将上下左右最接近的人类感染成僵尸,但不能穿墙。将所有人类感染为僵尸需要多久,如果不能感染所有人则返回 -1。

样例

给一个矩阵:

0 1 2 0 0
1 0 0 2 1
0 1 0 0 0

返回 2

代码

`

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

    int PEOPLE = 0;
    int ZOMBIE = 1;
    int WALL = 2;
    int[] detalX = {0, 0, 1, -1};
    int[] detalY = {1, -1, 0, 0};

    public int zombie(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;    //注意此处返回0
        }

        int m = grid.length;
        int n = grid[0].length;
        int people = 0;
        Queue<Coordinate> queue = new LinkedList<>();
        // 遍历矩阵,统计人的个数,并且把僵尸的位置加入队列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == PEOPLE) {
                    people++;
                }
                else if (grid[i][j] == ZOMBIE) {
                    queue.offer(new Coordinate(i, j));
                }
            }
        }

        // 注意特殊情况
        if (people == 0) {
            return 0;
        }

        int days = 0;
        while (!queue.isEmpty()) {
            // 分层来做,层数即天数
            days++;            
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 注意结点在第一个for里面抛出,不能写到for外面
                Coordinate zb = queue.poll();
                for (int direction = 0; direction < 4; direction++) {
                    Coordinate adj = new Coordinate(
                        zb.x + detalX[direction], 
                        zb.y + detalY[direction]);

                    // 接口形参应该是结点和矩阵
                    if (!isPeople(grid, adj)) {
                        continue;
                    }
                    grid[adj.x][adj.y] = ZOMBIE; 
                    people--;
                    if (people == 0) {
                        return days;
                    }
                    queue.offer(adj);
                }
            }
        }
        return -1;
    }

    private boolean isPeople(int[][] grid, Coordinate coor) {
        int m = grid.length;
        int n = grid[0].length;
        if (coor.x < 0 || coor.x > m - 1) {
            return false;
        }
        if (coor.y < 0 || coor.y > n - 1) {
            return false;
        }
        return (grid[coor.x][coor.y] == PEOPLE);
    }
}

`

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息