『剣指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)に入ることはできなかった.すみません、このロボットは何個の格子に達することができますか?
構想:本題はマトリクスの中の経路思想と一致し,いずれも遡及法を用いて問題を解決しているが,位置に対する制約条件の違いにすぎない.

    def movingCount(self, threshold, rows, cols):
        if rows < 1 or cols < 1 or threshold < 0:
            return 0
        visited = [False] * (rows * cols)
        return self.moving(threshold, rows, cols, 0, 0, visited)

    def moving(self, threshold, rows, cols, curx, cury, visited):
        cnt = 0
        if 0 <= curx < cols and 0 <= cury < rows and not visited[cury * cols + curx]:
            if self.calbitsum(curx) + self.calbitsum(cury) <= threshold:
                visited[cury * cols + curx] = True
                #            +             
                cnt = 1 + self.moving(threshold, rows, cols, curx - 1, cury, visited) \
                      + self.moving(threshold, rows, cols, curx, cury - 1, visited) \
                      + self.moving(threshold, rows, cols, curx + 1, cury, visited) \
                      + self.moving(threshold, rows, cols, curx, cury + 1, visited)
        return cnt

    def calbitsum(self, x):
        ressum = 0
        while x != 0:
            ressum += x % 10
            x /= 10
        return ressum