Introduction

In this article, you will learn about the Amazon interview question, 'How to find the turns needed for the zombies to colonize a 2-D matrix.'

Problem Statement

A matrix (2D array) has cells that are filled with one of three possible values, 0 implying the cell is empty, 1 implying the cell has a human in it and lastly, 2 implying the cell has a zombie in it. Every turn, the zombies infect any humans adjacent to them that might be up, down, left or right, and those humans become zombies. Those new zombies are then able to infect any humans next to then, and the cycle continues each turn. ​Given a matrix, to return the number of turns it takes until there are no humans left. And if any human survives, then return -1.
  1. static void Main(string[] args)
  2. {
  3. var colonize = new ColonizingZombies();
  4. var turnsTaken = colonize.FetchTurns(new int[,] {
  5. { 2, 1, 1 },
  6. { 0, 1, 1 },
  7. { 1, 0, 1 }
  8. });
  9. // turnsTaken is -1
  10. turnsTaken = colonize.FetchTurns(new int[,] {
  11. { 0, 2 }
  12. });
  13. // turnsTaken is 0
  14. turnsTaken = colonize.FetchTurns(new int[,] {
  15. { 2, 1, 1 },
  16. { 1, 1, 0 },
  17. { 0, 1, 1 }
  18. });
  19. // turnsTaken is 4
  20. }

Solution

Our approach towards the problem will be using multiple BFS (Breadth-First Search). We will update the matrix each turn by infecting humans next to any zombies. ​However, there are two things we need to watch out for, we must infect humans on the correct turns and we don't want to traverse empty cells unnecessarily. With this in mind, we'll use a list to hold each zombie, and for each zombie in the list, we'll process it by allowing it to infect any humans adjacent to it, meaning pushing that newly created zombie onto the queue to be processed later. However, the part where our code is going to become easier to read is that each Zombie in our list will store their matrix position [x-cordtinate, y-coordinate] and the turn it got infected. To do this, we'll have a special class to store this extra info. Here is the algorithm for the approach:
  1. Create a class named Zombie that stores integers Abscissa (x-coordinate), Ordinate (y-coordinate), and TurnInfected, and a list that holds Zombies.
  2. Traverse the matrix and if we see a zombie, add it to the queue (where TurnInfected = 0).
  3. Iterate over all the zombies in the list, update the current turn to be this zombie's TurnInfected and then infect any humans next to this zombie and add those new zombies to the list.
  4. Traverse the matrix to check if any humans survived.
  5. If any humans survived, return -1 or else, return the turns.
The C# pseudocode for this Amazon interview question is given below,
  1. class ColonizingZombies
  2. {
  3. public ColonizingZombies()
  4. {
  5. // create a list that holds zombies.
  6. Zombies = new List<Zombie>();
  7. }
  8. int[,] Grid;
  9. List<Zombie> Zombies;
  10. class Zombie
  11. {
  12. public int Abscissa;
  13. public int Ordinate;
  14. public int TurnInfected;
  15. }
  16. public int FetchTurns(int[,] grid)
  17. {
  18. Grid = grid;
  19. int turn = 0;
  20. // iterate the grid
  21. for (int i = 0; i < Grid.GetLength(0); i++)
  22. {
  23. for (int j = 0; j < Grid.GetLength(1); j++)
  24. {
  25. // if this cell has a zombie
  26. if (Grid[i, j] == 2)
  27. {
  28. // infect its neighbors
  29. AddZombieToQueue(i, j, 0);
  30. }
  31. }
  32. }
  34. // process each zombie in the queue by infecting any humans adjacent to it.
  35. foreach (var zombie in Zombies)
  36. {
  37. // update turn for last zombie
  38. turn = zombie.TurnInfected;
  40. // infecting any neighbors
  41. InfectNeighbors(zombie.Abscissa, zombie.Ordinate, zombie.TurnInfected + 1);
  42. }
  44. // check for any human survived
  45. bool humanSurvived = false;
  46. for (int i = 0; i < Grid.GetLength(0); i++)
  47. {
  48. for (int j = 0; j < Grid.GetLength(1); j++)
  49. {
  50. if (Grid[i, j] == 1)
  51. {
  52. humanSurvived = true;
  53. break;
  54. }
  55. }
  56. if (humanSurvived)
  57. break;
  58. }
  60. // if a human survived then return -1
  61. if (humanSurvived)
  62. return -1;
  64. // return the minute the last human got infected
  65. return turn;
  66. }
  67. void AddZombieToQueue(int x, int y, int turnInfected)
  68. {
  69. Grid[x, y] = 2;
  71. // Add this zombie
  72. Zombies.Add(new Zombie {
  73. Abscissa = x,
  74. Ordinate = y,
  75. TurnInfected = turnInfected
  76. });
  77. }
  79. void InfectNeighbors(int x, int y, int turnInfected)
  80. {
  81. // if found human, convert it to a zombie and add it to the queue.
  82. // for up
  83. if (x - 1 >= 0 && Grid[x - 1, y] == 1)
  84. AddZombieToQueue(x - 1, y, turnInfected);
  86. // for down
  87. if (x + 1 < Grid.GetLength(0) && Grid[x + 1, y] == 1)
  88. AddZombieToQueue(x + 1, y, turnInfected);
  90. // for left
  91. if (y - 1 >= 0 && Grid[x, y - 1] == 1)
  92. AddZombieToQueue(x, y - 1, turnInfected);
  94. // for right
  95. if (y + 1 < Grid.GetLength(1) && Grid[x, y + 1] == 1)
  96. AddZombieToQueue(x, y + 1, turnInfected);
  97. }
  98. }