• En
  • Signup
  • 刷题上岸
  • Today 0
  • Post 12
  • Followed 1
  • 捐助

    请在小工具里添加二维码

    刷题上岸 刷题上岸 关注:1 内容:12

    Amazon | OA 2019 | 🧟‍♀️ Zombie in Matrix

  • 查看作者
  • 打赏作者
  • 拉黑名单
    • 刷题上岸
    • 等级6
      土豪

      Given a 2D grid, each cell is either a zombie 1 or a human 0. Zombies can turn adjacent (up/down/left/right) human beings into zombies every hour. Find out how many hours does it take to infect all humans?

      Example:

      Input:
      [[0, 1, 1, 0, 1],
       [0, 1, 0, 1, 0],
       [0, 0, 0, 0, 1],
       [0, 1, 0, 0, 0]]
      
      Output: 2Explanation:
      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]]
      int minHours(int rows, int columns, List<List<Integer>> grid) {	// todo}

      Related problems:

      def minHour(rows, columns, grid):
          times=0
          Q=deque([])
          directions=[[1,0],[-1,0],[0,1],[0,-1]]
      
          for i in range(rows):
              for j in range(columns):
                  if grid[i][j]==1:
                      Q.append((i,j))
          
          while(Q):
              for _ in range(len(Q)):
                  x,y=Q.popleft()
                  for dir in directions:
                      i=x+dir[0]
                      j=y+dir[1]
                      if 0<=i<rows and 0<=j<columns and grid[i][j]==0:
                          grid[i][j]=1
                          Q.append((i,j)) 
              times+=1
          return max(0,times-1)

      请登录之后再进行评论

      登录
    • Tasks
    • Current Activities
    • Back to Top