Zombie in Matrix.

Also known as “Min hours to send file to all available servers”.

Description:

Given a 2D grid, each cell is either a zombie 1 or a human 0. (Or in case of the servers 1 means a server which already contains the file and 0 is an empty server). Zombies can turn adjacent (up/down/left/right) human beings into zombies every hour (server can send a file to adjacent server). Find out how many hours does it take to infect all humans (send the file to all servers)?

Example:

Input:
[[0, 1, 1, 0, 1],
 [0, 1, 0, 1, 0],
 [0, 0, 0, 0, 1],
 [0, 1, 0, 0, 0]]
Output: 2
Explanation:
At the end of the 1st hour, the status of the grid:
[[1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [0, 1, 0, 1, 1],
 [1, 1, 1, 0, 1]]
At the end of the 2nd hour, the status of the grid:
[[1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1]]

Solution:

Note that each zombie converts all humans around its position each hour. I solved this task for one human per one hour and then I spent some time to understand why my result is not the same as in the example. It is not described in the description but as I understand from the comments to this task in case of error the function should return -1.

This is a typical task about graph traversal. We should consider the matrix as a graph where each node is a cell of the matrix which connects by its edges to adjacent cells. If we can walk up/down/left/right each node has up to 4 edges if we can walk to diagonal cells — up to 8.

So in this task we should collect positions of all zombies (servers) and implement a graph traversal algorithm which starts from all these collected positions and will do one step for each round, that is each round each zombie will convert all adjacent humans into zombies (or send files to all adjacent servers).

There are two basic graph traversal algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS). For this case we should choose BFS algorithm because DFS will not allows so easily process all zombies in parallel.

Thus the algorithm looks like this:

1. Collect all positions of the zombies into a queue. Then we will use this queue for collecting positions of humans only.

2. Find adjacent humans around each enqueued position.

3. Add their positions into the queue.

4. Convert them into zombies.

5. Increase number of the hours.

6. Repeat from 2 until all humans on the matrix will be found and processed.

C++ code:

struct node_t { int row = 0, col = 0; };
int min_hours(vector<vector<int>> &matrix) {
    int hours = -1; // return -1 in case of error
    int directions[4][2] = {{1,  0}, {-1, 0}, {0,  1}, {0,  -1}};
    size_t rows = matrix.size();
    // to prevent access error when rows == 0
    size_t cols = rows ? matrix[0].size() : 0; 
    // collect all positions of the zombies into a queue
    queue<node_t> q;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 1) { q.push({i, j}); }
        }
    }
    // Do BFS until the end of the humans
    while (!q.empty()) {
        int q_size = q.size();
        // Process all positions which are already 
        // added into the queue.
        for (int i = 0; i < q_size; i++) {
            auto node = q.front();
            q.pop();
            // Find all humans in adjacent cells 
            // and add them into the queue
            for (auto dir: directions) {
                int nr = node.row + dir[0];
                int nc = node.col + dir[1];
                if (nr >= 0 && nr < rows && nc >= 0 && 
                    nc < cols && matrix[nr][nc] == 0) {
                    q.push({nr, nc});
                    matrix[nr][nc] = 1;
                }
            }
        }
        hours++;
    }
    return hours;
}

Full project you can find here: https://github.com/jolly-fellow/amazon/tree/master/zombie_in_matrix

Return to the table of contents.