Wednesday, February 15, 2017

Zombie in Matrix

In the 1st version of my solution, I traversed the matrix twice. The first traversal is to get all the zombies of the initial state, the second traversal is to check if there are any people left in the matrix.
This version is not optimal since it is wasteful to traverse the matrix twice.

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

public class Solution {
    /**
     * @param grid  a 2D integer grid
     * @return an integer
     */
    public int WALL = 2;
    public int ZOMBIE = 1;
    public int PEOPLE = 0;
    public int[] dX = {1, 0, -1, 0};
    public int[] dY = {0, 1, 0, -1};
    public int zombie(int[][] grid) {
        // Write your code here
        int days = 0;
        if (grid == null) {
            return days;
        }
        if (grid.length == 0 || grid[0].length == 0) {
            return days;
        }
        Queue<Point> que = new LinkedList<Point>();
       
        for (int x = 0; x < grid.length; x++) {
            for (int y = 0; y < grid[0].length; y++) {
                if (grid[x][y] == ZOMBIE) {
                    que.offer(new Point(x, y));
                }
            }
        }
       
        while(!que.isEmpty()) {
            days++;
            int size = que.size();
            for (int day = 0; day < size; day++) {
                Point curr = que.poll();
                for (int i = 0; i < 4; i++) {
                    int neighborX = curr.x + dX[i];
                    int neighborY = curr.y + dY[i];
                    Point neighbor = new Point(neighborX, neighborY);
                    if (isValid(grid, neighbor)) {
                        grid[neighborX][neighborY] = ZOMBIE;
                        que.add(neighbor);
                    }
                }
               
            }
        }
       
       
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == PEOPLE) {
                    return -1;
                }
            }
           
        }
        return days - 1;
    }
 
    public boolean isValid(int[][] grid, Point point) {
        if (point.x < 0 || point.x >= grid.length) {
            return false;
        }
        if (point.y < 0 || point.y >= grid[0].length) {
            return false;
        }
        return grid[point.x][point.y] == PEOPLE;
    }
}


-----------------------------------------------------
Improved version.
Count the number of people in the first traversal. Return when the number of people is reduced to zero.

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

public class Solution {
    /**
     * @param grid  a 2D integer grid
     * @return an integer
     */
    public int WALL = 2;
    public int ZOMBIE = 1;
    public int PEOPLE = 0;
    public int[] dX = {1, 0, -1, 0};
    public int[] dY = {0, 1, 0, -1};
    public int zombie(int[][] grid) {
        // Write your code here
        int days = 0;
        int people = 0;
        if (grid == null) {
            return days;
        }
        if (grid.length == 0 || grid[0].length == 0) {
            return days;
        }
        Queue<Point> que = new LinkedList<Point>();
       
        for (int x = 0; x < grid.length; x++) {
            for (int y = 0; y < grid[0].length; y++) {
                if (grid[x][y] == ZOMBIE) {
                    que.offer(new Point(x, y));
                }
                if (grid[x][y] == PEOPLE) {
                    people++;
                }
            }
        }
       
        while(!que.isEmpty()) {
            days++;
            int size = que.size();
            for (int day = 0; day < size; day++) {
                Point curr = que.poll();
                for (int i = 0; i < 4; i++) {
                    int neighborX = curr.x + dX[i];
                    int neighborY = curr.y + dY[i];
                    Point neighbor = new Point(neighborX, neighborY);
                    if (isValid(grid, neighbor)) {
                        grid[neighborX][neighborY] = ZOMBIE;
                        people--;
                        if (people == 0) {
                            return days;
                        }
                        que.add(neighbor);
                    }
                }
               
            }
        }
       
        return -1;
    }
 
    public boolean isValid(int[][] grid, Point point) {
        if (point.x < 0 || point.x >= grid.length) {
            return false;
        }
        if (point.y < 0 || point.y >= grid[0].length) {
            return false;
        }
        return grid[point.x][point.y] == PEOPLE;
    }
}


No comments:

Post a Comment