BFS Matrix

Catalogue

1. 1. 490. The Maze
2. 2. 296. Best Meeting Point
   1. 2.1. Solution1. Sort
   2. 2.2. Solution2. BFS - TLE
3. 3. 317. Shortest Distance from All Buildings

490. The Maze

• Directions BFS

  class Solution(object):
      def hasPath(self, maze, start, destination):
          m, n = len(maze), len(maze[0])
          queue = collections.deque([(start)])
          visited = set()
          visited.add(tuple(start))
          dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]
          while queue:
              x, y = queue.popleft()
              if (x, y) == tuple(destination):
                  return True
              for dx, dy in dirs:
                  nx, ny = x, y
                  while 0 <= nx + dx <= m-1 and 0 <= ny + dy <= n-1 and maze[nx+dx][ny+dy] == 0:
                      nx += dx
                      ny += dy
  
                  if (nx, ny) not in visited:
                      queue.append((nx, ny))
                      visited.add((nx, ny))
          return False

296. Best Meeting Point

Solution1. Sort

• Time : O(mn), Space : O(mn)
• Only for this case that we do not have any obstacle and distance is Manhattan Distance

class Solution:
    def minTotalDistance(self, grid):
        xnums, ynums = [], []
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    xnums.append(i)
                    ynums.append(j)

        return self.minDistance(xnums) + self.minDistance(ynums)

    def minDistance(self, nums):
        nums = sorted(nums)
        res = 0
        left, right = 0, len(nums)-1
        while left < right:
            res += nums[right] - nums[left]
            right -= 1
            left += 1
        return res

Solution2. BFS - TLE

• Time : O($(mn)^2$), Space : O(mn)
• More General Solution, But have high time complexity!!

  class Solution:
      def minTotalDistance(self, grid):
          m, n = len(grid), len(grid[0])
          self.dis = [[0] * n for _ in range(m)]
          for i in range(m):
              for j in range(n):
                  if grid[i][j] == 1:
                      self.bfs(grid, i, j)
          return min([self.dis[i][j] for i in range(m) for j in range(n)])
  
      def bfs(self, grid, i, j):
          queue = collections.deque([(i, j, 0)])
          visited = set([(i, j)])
          while queue:
              ni, nj, d = queue.popleft()
              self.dis[ni][nj] += d
  
              for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                  if (0 <= ni+di <= len(grid)-1 and
                      0 <= nj+dj <= len(grid[0])-1 and
                      (ni+di, nj+dj) not in visited):
                      queue.append((ni+di, nj+dj, d+1))
                      visited.add((ni+di, nj+dj))

317. Shortest Distance from All Buildings

• Key idea : people to building or building to people ?

  class Solution(object):
      def shortestDistance(self, grid):
          m, n = len(grid), len(grid[0])
          sums = collections.defaultdict(int)
          bcnt = collections.defaultdict(int)
          total = 0
          directions = [(-1,0), (0,-1), (0,1), (1,0)]
          for i in xrange(m):
              for j in xrange(n):
                  if grid[i][j] == 1: # Run BFS
                      total += 1
                      visited = set()
                      queue = [(i,j,0)]
                      while queue:
                          x, y, val = queue.pop(0)
                          for dx, dy in directions:
                              if 0 <= x+dx <= m-1 and 0 <= y+dy <= n-1 and (x+dx, y+dy) not in visited and grid[x+dx][y+dy] == 0:
                                  visited.add((x+dx, y+dy))
                                  queue.append((x+dx, y+dy, val+1))
                                  sums[(x+dx, y+dy)] += val+1
                                  bcnt[(x+dx, y+dy)] += 1
          res = float('inf')
          for x, y in bcnt.keys():
              if bcnt[(x, y)] == total:
                  res = min(res, sums[(x, y)])
          return -1 if res == float('inf') else res

• where to add visited in BFS? when pop out or push in?
• add visited hash set when you append an element in the queue!!!

class Solution(object):
    def shortestDistance(self, grid):
        if not grid:
            return -1

        m, n = len(grid), len(grid[0])
        matrix = [[[0, 0] for _ in range(n)] for _ in range(m)]
        cnt = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    self.bfs(matrix, i, j, grid)
                    cnt += 1
        res = float('inf')            
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0 and matrix[i][j][1] == cnt:
                    res = min(res, matrix[i][j][0])
        return -1 if res == float('inf') else res

    def bfs(self, matrix, i, j, grid):
        m, n = len(grid), len(grid[0])
        queue = collections.deque([(i, j, 0)])
        visited = set()
        visited.add((i, j))
        while queue:
            x, y, step = queue.popleft()
            matrix[x][y][0] += step
            matrix[x][y][1] += 1
            for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                nx, ny = x+dx, y+dy
                if 0 <= nx <= m-1 and 0 <= ny <= n-1 and (nx, ny) not in visited and grid[nx][ny] == 0:
                    queue.append((nx, ny, step+1))
                    visited.add((nx, ny))