剑指Offer 13 机器人的运动范围

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     def __init__(self):
 4         self.visited = []
 5         self.count = 0
 6         
 7     def dfs(self,threshold,rows,cols,i,j,direction):
 8         if i < 0 or i >= rows or j < 0 or j >= cols:
 9             return
10         elif self.visited[i][j] == 1:
11             return
12         else:
13             self.visited[i][j] = 1
14             num = 0
15             for n1 in str(i):
16                 num += int(n1)
17             for n2 in str(j):
18                 num += int(n2)
19             if num <= threshold:
20                 self.count += 1
21                 for direct in direction:
22                     x = i+direct[0]
23                     y = j+direct[1]
24                     self.dfs(threshold,rows,cols,x,y,direction)
25         
26     def movingCount(self, threshold, rows, cols):
27         self.visited = [[0 for c in range(cols)]for r in range(rows)]
28         direction = [[0,1],[0,-1],[1,0],[-1,0]]
29         self.dfs(threshold,rows,cols,0,0,direction)
30         return self.count
31         # write code here