dfs 两种方法

两种方法

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, k, r, c):
        # write code here
        self.cnt = 0
        if r == 0 or c == 0: return 0

        def p_sum(x, y):
            res = 0
            while x:
                res += x%10
                x = x//10

            while y:
                res += y%10
                y = y//10
            return res <= k


        mat = [[1 for _ in range(c)] for _ in range(r)]

        def dfs(i, j):
            if not (0<=i<r and 0<=j<c): return 0
            if mat[i][j] == 0: return 0
            if not p_sum(i, j): return 0
            s = 1
            mat[i][j] = 0
            s += dfs(i+1, j)
            s += dfs(i-1, j)
            s += dfs(i, j-1)
            s += dfs(i, j+1)
            #mat[i][j] = 1
            return s

        return dfs(0, 0)

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, k, r, c):
        # write code here
        self.cnt = 0
        if r == 0 or c == 0: return 0

        def p_sum(x, y):
            res = 0
            while x:
                res += x%10
                x = x//10

            while y:
                res += y%10
                y = y//10
            return res <= k


        mat = [[1 for _ in range(c)] for _ in range(r)]

        def dfs(i, j):
            if not (0<=i<r and 0<=j<c): return 
            if mat[i][j] == 0: return 
            if not p_sum(i, j): return 
            assert mat[i][j] == 1
            self.cnt += 1
            mat[i][j] = 0
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j-1)
            dfs(i, j+1)


        dfs(0, 0)
        return self.cnt