机器人的运动范围

# -*- coding:utf-8 -*-
class Solution:
    def getSum(self,x,y):
        sum = 0
        for a in [x,y]:
            while a // 10 != 0:
                sum += a%10
                a = a//10
            sum += a
        return sum
    def if_going(self, x,y):
        return (0<=x<=self.rows-1 and 0<=y<=self.cols-1 and (x,y) not in self.visited
               and self.getSum(x, y)<=self.threshold)
    def movingCountCore(self, x,y):
        count = 0
        if self.if_going(x, y):
            self.visited[(x,y)] = True
            count = 1+self.movingCountCore(x-1,y)+self.movingCountCore(x+1,y)+\
            self.movingCountCore(x,y+1)+self.movingCountCore(x,y-1)
        return count
    def movingCount(self, threshold, rows, cols):
        assert rows>=0 and cols >=0
        self.threshold = threshold
        self.visited = {}
        self.rows = rows
        self.cols = cols
        return self.movingCountCore(0, 0)

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
        self.threshold = threshold
        self.rows, self.cols = rows, cols
        self.dict = {}
        self.dfs(0, 0)
        return len(self.dict)
        
    def get_sum(self, i, j):
        num = 0
        while i:
            temp = i%10
            i //= 10
            num += temp
        while j:
            temp = j%10
            j //= 10
            num += temp
        return num
    
    def dfs(self, i, j):
        if i>=self.rows&nbs***bsp;j>=self.cols:   # 越界
            return 
        if self.get_sum(i, j)>self.threshold:   # 超过阈值
            return
        if self.dict.get((i,j)):   # 规避重复路径
            return
        self.dict[(i,j)] = 1   # 走过了就添加key
        self.dfs(i+1, j)   # 因为我们是从0，0开始，所有只需要走下、右即可
        self.dfs(i, j+1)

python解法：

# -*- coding:utf-8 -*-
'''
解法：可以用dfs或者bfs做，不会，树等最后再做；
'''
class Solution:
    def getsum(self,num):
            sum = 0
            while num > 0:
                sum += num % 10
                num /= 10
            return sum
    def movingCount(self, threshold, rows, cols):
        count = 0
        for i in range(rows):
            for j in range(cols):
                if self.getsum(i) + self.getsum(j) <= threshold:
                    count += 1
                # emmm，但是这代码作何解释呢？
                elif rows == 1 or cols == 1:
                    return count
        return count

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
        t = 0
        #注意别把range(rows)写成rows!!!
        for i in range(rows):
            for j in range(cols):
                if self.calSum(i) + self.calSum(j)<= threshold:
                    t += 1
                #当只有一行一列时，直接结束遍历
                elif (rows==1&nbs***bsp;cols==1):
                    return t 
        return t
        
    def calSum(self,num):
        sum = 0
        while num :
            sum += num % 10
            num = num // 10
        return sum
    

BFS遍历地图，找到从(0,0)开始的所有满足条件的可达点。
[!] 注意考虑k<0的情况，这种情况下(0,0)都不可达。

# -*- coding:utf-8 -*-
class Solution:
    def check(self, x, y, k):
        res = 0
        while x!=0 or y!=0:
            res += x%10
            x //= 10
            res += y%10
            y //= 10
        return res<=k
    def movingCount(self, threshold, rows, cols):
        # write code here
        #BFS
        pos = [(0, 0)]
        flag = [[0 for i in range(cols)] for j in range(rows)]  # 判断是否走过
        if threshold < 0:
            return 0
        cnt = 1
        flag[0][0] = 1
        while len(pos)!=0:
            x, y = pos[0]
            del(pos[0])
            if y+1<cols and flag[x][y+1]==0 and self.check(x, y+1, threshold):
                pos.append((x, y+1))
                flag[x][y+1] = 1
                cnt += 1
            if y-1>=0 and flag[x][y-1]==0 and self.check(x, y-1, threshold):
                pos.append((x, y-1))
                flag[x][y-1] = 1
                cnt += 1
            if x+1<rows and flag[x+1][y]==0 and self.check(x+1, y, threshold):
                pos.append((x+1, y))
                flag[x+1][y] = 1
                cnt += 1
            if x-1>=0 and flag[x-1][y]==0 and self.check(x-1, y, threshold):
                pos.append((x-1, y))
                flag[x-1][y] = 1
                cnt += 1
        return cnt

class Solution:
    def movingCount(self, k, m, n):
        q = []
        s = set()
        q.append((0, 0))
        while len(q) > 0:
            x, y = q.pop(0)
            if not (x, y) in s and 0 <= x < m and 0 <= y < n \
                    and sum(map(int, str(x))) + sum(map(int, str(y))) <= k:
                s.add((x, y))
                for nx, ny in [(x + 1, y), (x, y + 1)]:
                    q.append((nx, ny))
        return len(s)

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # 计算每一位之和
        def getsum(num):
            sum = 0
            while num>0:
                sum += num%10
                num = num//10
            return sum
        path = []
        def back(start):
            if start in path or getsum(start[0]) + getsum(start[1])> threshold:
                return None
            if start[0]>=rows or start[1]>=cols:
                return None
            path.append(start)       # 从0，0开始向右向下遍历，减少走回头路的次数             
            back([start[0]+1,start[1]])
            back([start[0],start[1]+1])
        back([0,0])
        return len(path) 
           

class Solution:
    def movingCount(self, threshold, rows, cols):
        matrix = [[0 for i in range(cols)] for j in range(rows)]
        def numberCount(m):
            n = 0
            while m:
                n += m%10
                m = m//10
            return n
        matrix[0][0] = 1
        if threshold <= 0:
            return 0
        else:
            for i in range(rows):
                for j in range(cols):
                    if numberCount(i) + numberCount(j) <= threshold and (matrix[i][j-1]==1&nbs***bsp;matrix[i-1][j]==1):
                        matrix[i][j] = 1
        return sum(map(sum,matrix))

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        x = [[0 for _ in range(cols)] for _ in range(rows)]
        self.check_cell(threshold, 0, 0,rows,cols,x)
        
        res = 0
        for i in range(rows):
            res += sum(x[i])
        return res
    
    def check_cell(self, k, i, j,rows,cols,x):
        if self.check_sum(k,i,j):
            x[i][j] = 1
            if i > 0 and x[i-1][j] == 0 and self.check_sum(k,i-1,j):
                self.check_cell(k,i-1,j,rows,cols,x)
            if i < rows -1 and x[i+1][j] == 0 and self.check_sum(k,i+1,j):
                self.check_cell(k,i+1,j,rows,cols,x)
            if j > 0  and x[i][j-1] == 0 and self.check_sum(k,i,j-1):
                self.check_cell(k,i,j-1,rows,cols,x)
            if j < cols -1 and x[i][j+1] == 0 and self.check_sum(k,i,j+1):
                self.check_cell(k,i,j+1,rows,cols,x)
    def check_sum(self,k,i,j):
        row_sum = 0
        col_cum = 0
        while i != 0 :
            row_sum += i % 10
            i //= 10
        while j != 0:
            col_cum += j % 10
            j //= 10
        if row_sum + col_cum <= k:
            return True
        return False
    

# -*- coding:utf-8 -*-
class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
        if threshold<0&nbs***bsp;rows<1&nbs***bsp;cols<1:
            return 0
        #用来表示该格子是否被走过
        visited=[0 for i in range(rows*cols)]
        #从（0,0）起点，开始走起
        count1=self.movingCountcore(threshold, rows, cols,0,0,visited)
        return count1
    def movingCountcore(self, threshold, rows, cols,row,col,visited):
        count1=0
        if self.checkcore(threshold,rows,cols,row,col,visited):
            #首先检验该格子是否符合条件
            visited[row*cols+col]=1
            #递归方法的一个简单应用，求总体的行走轨迹，只需要现在的占据的格子，加上在四个方向上的行走轨迹
            count1=1+self.movingCountcore(threshold, rows, cols,row,col-1,visited) \
              +self.movingCountcore(threshold, rows, cols,row,col+1,visited) \
              +self.movingCountcore(threshold, rows, cols,row-1,col,visited) \
              +self.movingCountcore(threshold, rows, cols,row+1,col,visited)
        return count1
    def checkcore(self,threshold,rows,cols,row,col,visited):
        if row>=0 and row<rows and col>=0 and col<cols and self.numbercount(row)+self.numbercount(col)<=threshold and not visited[row*cols+col]:
            return True
        return False
    def numbercount(self,number):
        sumnum=0
        while(number>0):
            sumnum+=number%10
            number=number/10
        return sumnum

# -*- coding:utf-8 -*-
# 解题思路：深度优先搜索，一个格子的准入条件为下标不越界；并且各位数之和不超出给定的值；并且没有被进入过
# 从(0,0)开始计算可以进入的格子的个数为每个格子4个方向上可以进入的格子数+1；
# 为保证格子不能被重复进入，使用visited数组记录格子是否被进入过
class Solution:
    def movingCount(self, threshold, rows, cols):
        # write code here
        if rows < 0&nbs***bsp;cols < 0&nbs***bsp;threshold < 0:
            return 0

        visited = [[False for j in range(cols)] for i in range(rows)]

        def compute_sum(row, col):
            sum = 0

            while row:
                sum += row % 10
                row = row // 10

            while col:
                sum += col % 10
                col = col // 10

            return sum

        def canInter(row, col):
            if 0 <= row < rows and 0 <= col < cols and compute_sum(row, col) <= threshold and not visited[row][col]:
                return True

            return False

        def compute_count(row, col):
            count = 0

            if canInter(row, col):
                visited[row][col] = True
                count = 1 + compute_count(row - 1, col) + compute_count(row, col + 1) + compute_count(row + 1, col) \
                        + compute_count(row, col - 1)

            return count

        return compute_count(0, 0)
    

class Solution:
    def __init__(self):
        self.cnt=0

    def movingCount(self, threshold, rows, cols):
        matrix=[[i+j*cols for i in range(cols)]for j in range(rows)]
        self.dfs(threshold,rows,classmethod,0,0,matrix)
        return self.cnt


    def dfs(self,threshold,rows,cols,i,j,matrix):
        if self.check_valid(threshold,rows,cols,i,j,matrix):
            self.cnt+=1
            matrix[i][j]=None   # 痛苦地调了半天，发现是=写成了==号
            print(matrix)
            self.dfs(threshold,rows,cols,i,j+1,matrix)
            self.dfs(threshold,rows,cols,i,j-1,matrix)
            self.dfs(threshold,rows,cols,i-1,j,matrix)
            self.dfs(threshold,rows,cols,i+1,j,matrix)

    def check_valid(self,threshold,rows,cols,i,j,matrix):
        try:
            if matrix[i][j]!=None and self.get_digit_sum(i,j)<=threshold:return True
            else:return False
        except:  # 这种情况是数组越界，用try catch写起来很简单
            return False

    def get_digit_sum(self,i,j):
        return reduce(lambda x,y:x+y,map(lambda x:int(x),str(i)+str(j))) # 求数位和一行搞定爽不爽