DFS - Matrix

Catalogue

1. 1. 329. Longest Increasing Path in a Matrix
2. 2. 36. Valid Sudoku
3. 3. 37. Sudoku Solver
4. 4. 489. Robot Room Cleaner
5. 5.

329. Longest Increasing Path in a Matrix

• DFS search + Memorization in Matrix!!!

# Time : O(mn), Space : O(mn)
class Solution:
    def longestIncreasingPath(self, matrix):
        if not matrix:
            return 0

        m, n = len(matrix), len(matrix[0])
        self.visited = {}
        res = 0
        for i in range(m):
            for j in range(n):
                ans = self.dfs(matrix, -float('inf'), i, j)
                res = max(res, ans)
        return res


    def dfs(self, matrix, prev, i, j):
        m, n = len(matrix), len(matrix[0])
        if i < 0 or j < 0 or i > m-1 or j > n-1:
            return 0

        val = matrix[i][j]
        if val <= prev:
            return 0

        if (i, j) in self.visited:
            return self.visited[(i, j)]

        d1 = self.dfs(matrix, val, i+1, j)
        d2 = self.dfs(matrix, val, i, j+1)
        d3 = self.dfs(matrix, val, i-1, j)
        d4 = self.dfs(matrix, val, i, j-1)
        d = max(d1, d2, d3, d4) + 1
        self.visited[(i, j)] = d
        return d

36. Valid Sudoku

• but only meet the condition showed below can Not make sure the sudoku is valid!!!

  class Solution:
      def isValidSudoku(self, board):
          rows = [set() for _ in range(9)]
          cols = [set() for _ in range(9)]
          cubs = [set() for _ in range(9)]
          for i in range(9):
              for j in range(9):
                  if board[i][j] == '.':
                      continue
                  num = board[i][j]
                  c = i // 3 * 3 + j // 3
  
                  if num in rows[i] or num in cols[j] or num in cubs[c]:
                      return False
  
                  rows[i].add(num)
                  cols[j].add(num)
                  cubs[c].add(num)
          return True

37. Sudoku Solver

class Solution:
    def solveSudoku(self, board):
        self.solve(board)

    def solve(self, board):
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    continue

                for ch in list("123456789"):
                    if self.isValid(board, i, j, ch):
                        board[i][j] = ch
                        if self.solve(board):
                            return True
                        else:
                            board[i][j] = '.'
                return False
        return True

    def isValid(self, board, i, j, ch):
        # row & col
        for k in range(9):
            if board[i][k] == ch:
                return False

            if board[k][j] == ch:
                return False

        # cubes
        row, col = (i // 3) * 3, (j // 3) * 3
        for r in range(3):
            for c in range(3):
                if board[row + r][col + c] == ch:
                    return False
        return True

class Solution:
    def solveSudoku(self, board):
        self.solve(board)

    def solve(self, board):
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    continue

                candidates = self.getCandidates(board, i, j)
                for ch in candidates:
                    board[i][j] = ch
                    if self.solve(board):
                        return True
                    else:
                        board[i][j] = '.'
                return False
        return True

    def getCandidates(self, board, i, j):
        cans = set(list("123456789"))
        for k in range(9):
            ch = board[i][k]
            if ch != '.' and ch in cans:
                cans.remove(board[i][k])

            ch = board[k][j]
            if ch != '.' and ch in cans:
                cans.remove(board[k][j])

        row, col = (i // 3) * 3, (j // 3) * 3
        for r in range(3):
            for c in range(3):
                ch = board[row + r][col + c]
                if ch != '.' and ch in cans:
                    cans.remove(ch)
        return list(cans)

489. Robot Room Cleaner

• The main different thing between this dfs and others is that you have to Maintain the Direction!!!
• Backtrack: turn 2 times to revert, move 1 step, and turn 2 times to revert back.

  class Solution(object):
      def cleanRoom(self, robot):
          visited = set()
          self.dfs(robot, 0, 0, 0, visited)
  
      def dfs(self, robot, i, j, k, visited):
          robot.clean()
          visited.add((i, j))
  
          dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
          for _ in range(4):
              di, dj = dirs[k]
              ni, nj = i + di, j + dj
              if (ni, nj) not in visited and robot.move():
                  self.dfs(robot, ni, nj, k, visited)
                  robot.turnLeft()
                  robot.turnLeft()
                  robot.move()
                  robot.turnLeft()
                  robot.turnLeft()
              robot.turnLeft()
              k = (k + 1) % 4