美文网首页
LintCode题解 | 亚马逊在线测试真题:僵尸矩阵

LintCode题解 | 亚马逊在线测试真题:僵尸矩阵

作者: SunnyZhao2019 | 来源:发表于2020-02-19 19:13 被阅读0次

    【题目描述】

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

    【题目样例】

    例1:

    输入:
    [[0,1,2,0,0],
    [1,0,0,2,1],
    [0,1,0,0,0]]

    输出:
    2

    例2:

    输入:
    [[0,0,0],
    [0,0,0],
    [0,0,1]]

    输出:
    4

    【评测与题解】

    →戳这里在线评测及查看题解

    /**
    * 本参考程序来自九章算法,由 @九章算法 提供。版权所有,转发请注明出处。
    * - 九章算法致力于帮助更多中国人找到好的工作,教师团队均来自硅谷和国内的一线大公司在职工程师。
    * - 现有的面试培训课程包括:九章算法班,系统设计班,算法强化班,Java入门与基础算法班,Android 项目实战班,
    * - Big Data 项目实战班,算法面试高频题班, 动态规划专题班
    * - 更多详情请见官方网站:http://www.jiuzhang.com/?source=code
    */ 
    
    class Coordinate {
        int x, y;
        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public class Solution {
        public int PEOPLE = 0;
        public int ZOMBIE = 1;
        public int WALL = 2;
        
        public int[] deltaX = {1, 0, 0, -1};
        public int[] deltaY = {0, 1, -1, 0};
         
        /**
         * @param grid a 2D integer grid
         * @return an integer
         */
        public int zombie(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) {
                return 0;
            }
            
            int n = grid.length;
            int m = grid[0].length;
            
            // initialize the queue & count people
            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] == PEOPLE) {
                        people++;
                    } else if (grid[i][j] == ZOMBIE) {
                        queue.offer(new Coordinate(i, j));
                    }
                }
            }
            
            // corner case
            if (people == 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] = ZOMBIE;
                        people--;
                        if (people == 0) {
                            return days;
                        }
                        queue.offer(adj);
                    }
                }
            }
            
            return -1;
        }
        
        private 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] == PEOPLE);
        }
    }
    
    //version 硅谷算法班
    public class Solution {
        /**
         * @param grid: a 2D integer grid
         * @return: an integer
         */
        public int zombie(int[][] grid) {
            // write your code here
            if (grid == null || grid.length == 0 || grid[0].length == 0) {
                return 0;
            }
            Queue<Integer> qx = new LinkedList<>();
            Queue<Integer> qy = new LinkedList<>();
            boolean[][] v = new boolean[grid.length][grid[0].length];
    
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 1) {
                        qx.offer(i);
                        qy.offer(j);
                        v[i][j] = true;
                    }
                }
            }
    
            int[] dx = {1, -1, 0, 0};
            int[] dy = {0, 0, 1, -1};
    
            int dist = 0;
            while (!qx.isEmpty()) {
                dist++;
                int size = qx.size();
                for (int i = 0; i < size; i++) {
                    int cx = qx.poll();
                    int cy = qy.poll();
                    for (int k = 0; k < 4; k++) {
                        int nx = cx + dx[k];
                        int ny = cy + dy[k];
                        if (0 <= nx && nx < grid.length && 0 <= ny && ny < grid[0].length && grid[nx][ny] == 0 && !v[nx][ny]) {
                            qx.offer(nx);
                            qy.offer(ny);
                            v[nx][ny] = true;
                        }
                    }
                }
            }
            dist--;
    
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 0 && !v[i][j]) {
                        return -1;
                    }
                }
            }
    
            return dist;
        }
    }
    

    相关文章

      网友评论

          本文标题:LintCode题解 | 亚马逊在线测试真题:僵尸矩阵

          本文链接:https://www.haomeiwen.com/subject/nqczfhtx.html