難度：中等

題目內(nèi)容：

地上有一個(gè)m行n列的方格，從坐標(biāo) [0,0] 到坐標(biāo) [m-1,n-1] 。一個(gè)機(jī)器人從坐標(biāo) [0, 0] 的格子開始移動(dòng)，它每次可以向左、右、上、下移動(dòng)一格（不能移動(dòng)到方格外），也不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。例如，當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格 [35, 37] ，因?yàn)?+5+3+7=18。但它不能進(jìn)入方格 [35, 38]，因?yàn)?+5+3+8=19。請問該機(jī)器人能夠到達(dá)多少個(gè)格子？

示例 1：

輸入：m = 2, n = 3, k = 1
輸出：3
示例 1：

輸入：m = 3, n = 1, k = 0
輸出：1
提示：

1 <= n,m <= 100
0 <= k <= 20

題解：

emmm那以6為例的話

image.png

可以看出大概就是這個(gè)形狀，所以直接加就好了
如果行數(shù)和列數(shù)都比7大那就能取個(gè)三角形
如果不夠就得截取

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        if m >= k +1 and n >= k + 1:
            return self.calTri(k+1)
        elif m >=k+1 and n < k+1:
            return self.calTri(k+1) - self.calTri(k+1-n)
        elif m < k+1 and n >=k+1:
            return self.calTri(k+1) - self.calTri(k+1-m)
        elif m + n >  k+1:
            return self.calTri(k+1) - self.calTri(k+1-m) - self.calTri(k+1-n) 
        else:
            return m*n
    def calTri(self,x):
        return int((1 + x)*x/2)

那就可以很簡單的做出了
不過雖然數(shù)學(xué)方法又簡單又高效
但是對編程知識幫助不是很大
還是應(yīng)該用BFS之類的編程方法嘗試一下實(shí)現(xiàn)