【剣指offer】ロボットの動き範囲――Python実現

【題目説明】地上にはm行とn列の格子がある.1つのロボットは座標0,0の格子から移動し始め、毎回左、右、上、下の4つの方向に1格しか移動できませんが、行座標と列座標の数位の和がkより大きい格子に入ることはできません.例えば、kが18である場合、3+5+3+7=18であるため、ロボットは格子(35,37)に入ることができる.しかし,3＋5＋3＋8＝19のため,格子(35,38)に入ることはできなかった.すみません、このロボットは何個の格子に達することができますか?
【解題構想】この問題には2つの実現方式があり、1つはdfs再帰解であり、1つは直接遍歴し、直接遍歴する方法が簡単であるため、ここではdfs再帰解を用いる方法を述べ、座標0,0のノードから遍歴するので、右と下を遍歴すればよいので、すべてのノードを遍歴することができ、この位置にアクセスしたかどうかを1つのvisited配列で記録すればよい.Pythonで実装されたコードは以下の通りです.

# -*- coding:utf-8 -*-
class Solution:
    def dfs(self, x, y, threshold, rows, cols):
        if x>=rows or x<0 or y>=cols or y<0 or visited[x][y] or self.count(x)+self.count(y)>threshold:
            return False
        visited[x][y] = 1
        return self.dfs(x+1, y, threshold, rows, cols) + self.dfs(x, y+1, threshold, rows, cols) + 1
    
    def count(self, num):
        res = 0
        while num:
            res += num%10
            num /= 10
        return res
    
    def movingCount(self, threshold, rows, cols):
        # write code here
        global visited
        visited = [[0 for j in range(cols)] for i in range(rows)]
        return self.dfs(0, 0, threshold, rows, cols)