劍指offer 66. 機器人的運動範圍

描述

地上有一個rows行和cols列的方格。坐标從 [0,0] 到 [rows-1,cols-1]。一個機器人從坐标0,0的格子開始移動，每一次隻能向左，右，上，下四個方向移動一格，但是不能進入行坐标和列坐标的數位之和大于threshold的格子。 例如，當threshold為18時，機器人能夠進入方格[35,37]，因為3+5+3+7 = 18。但是，它不能進入方格[35,38]，因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？

範圍:

1 <= rows, cols<= 100

0 <= threshold <= 20

示例1

輸入：

1,2,3

傳回值：

3

示例2

輸入：

0,1,3

傳回值：

1

示例3

輸入：

10,1,100

傳回值：

29

說明：

[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 這29種，後面的[0,29],[0,30]以及[0,31]等等是無法到達的

第一種，遞歸深度優先

# -*- coding:utf-8 -*-
class Solution:
    
    def __init__(self):
        self.visit = [[0 for j in range(100)] for i in range(100)]
    
    def getSum(self, v):
        res=0
        while v>0:
            res += (v%10)
            v=v/10
        return res
    
    def move(self, threshold, rows, cols, row, col, visited):
        if row<0 or row>=rows or col<0 or col>=cols:
            return 0
        if self.getSum(row) + self.getSum(col) > threshold:
            return 0
        if visited[row][col]==1:
            return 0
        visited[row][col]=1
        self.visit[row][col]=1
        downward = self.move(threshold, rows, cols, row+1, col, visited)
        upward = self.move(threshold, rows, cols, row-1, col, visited)
        right = self.move(threshold, rows, cols, row, col+1, visited)
        left = self.move(threshold, rows, cols, row, col-1, visited)
#         visited[row][col]=0
        return downward + upward + right + left + 1
    
    def movingCount(self, threshold, rows, cols):
        # write code here
        if rows == 0 or cols ==0:
            return 0
        if threshold == 0:
            return 1
        res = 0
        for i in range(rows):
            for j in range(cols):
                if self.visit[i][j] == 0:
                    visited = [[0 for t1 in range(cols)] for t2 in range(rows)]
                    cnt = self.move(threshold, rows, cols, i, j, visited)
                    if res < cnt:
                        res = cnt
        return res
                    
           

第二種方式， 廣度優先

# -*- coding:utf-8 -*-
class Solution:
    def isLessThanThreshold(self, threshold, r, c):
        res = 0
        while r>0:
            res += (r%10)
            r = r/10
        while c>0:
            res += (c%10)
            c = c/10
        if res <= threshold:
            return True
        return False
    
    def isValid(self, r, c, rows, cols, threshold):
        if r<0 or r>=rows or c<0 or c>=cols:
            return False
        return self.isLessThanThreshold(threshold, r, c)
    
    def movingCount(self, threshold, rows, cols):
        # write code here
        if rows == 0 or cols == 0:
            return 0
        if threshold == 0:
            return 1
        s = []
        s.append((0,0))
        visited = [[0 for j in range(cols)] for i in range(rows)]
        visited[0][0] = 1
        res = 0
        while len(s)>0:
            r, c = s.pop()
            res += 1
            if self.isValid(r+1, c, rows, cols, threshold) and visited[r+1][c]==0:
                visited[r+1][c]=1
                s.append((r+1, c))
            if self.isValid(r-1, c, rows, cols, threshold) and visited[r-1][c]==0:
                visited[r-1][c]=1
                s.append((r-1, c))
            if self.isValid(r, c+1, rows, cols, threshold) and visited[r][c+1]==0:
                visited[r][c+1]=1
                s.append((r, c+1))
            if self.isValid(r, c-1, rows, cols, threshold) and visited[r][c-1]==0:
                visited[r][c-1]=1
                s.append((r, c-1))
        return res