地上有一個(gè)m行n列的方格，從坐標(biāo) [0,0] 到坐標(biāo) [m-1,n-1] 。一個(gè)機(jī)器人從坐標(biāo) [0, 0] 的格子開(kāi)始移動(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)?strong>3+5+3+7=18。但它不能進(jìn)入方格 [35, 38]，因?yàn)?strong>3+5+3+8=19。請(qǐng)問(wèn)該機(jī)器人能夠到達(dá)多少個(gè)格子？

示例

• 輸入：m = 2, n = 3, k = 1

• 輸出：3

提示

• 1 <= n,m <= 100

• 0 <= k <= 20

解題思路

本題與 矩陣中的路徑 類(lèi)似，是典型的 搜索 & 回溯問(wèn)題。在介紹回溯算法算法前，為提升計(jì)算效率，首先講述兩項(xiàng)前置工作： 數(shù)位之和計(jì)算 、 可達(dá)解分析 。

數(shù)位之和計(jì)算

由于機(jī)器人每次只能移動(dòng)一格（即只能從 x 運(yùn)動(dòng)至 x±1），因此每次只需計(jì)算 x 到 x±1 的數(shù)位和增量。本題說(shuō)明 1≤n,m≤100 ，以下公式僅在此范圍適用。

數(shù)位和增量公式：

• 設(shè) x 的數(shù)位和為 sx，x+1 的數(shù)位和為 s(x+1)；

• 當(dāng) (x+1)%10=0 時(shí)： s(x+1) = sx ? 8 ，例如 19, 20 的數(shù)位和分別為 10, 21；

• 當(dāng) (x+1)%10 =0 時(shí)：s(x+1) = sx +1 ，例如 1, 2 的數(shù)位和分別為 1, 2 。

以下代碼為增量公式的三元表達(dá)式寫(xiě)法，將整合入最終代碼中。

(x + 1) % 10 != 0 ? s_x + 1 : s_x - 8;

可答解分析

根據(jù)數(shù)位和增量公式得知，數(shù)位和每逢 進(jìn)位 突變一次。根據(jù)此特點(diǎn)，矩陣中 滿(mǎn)足數(shù)位和的解 構(gòu)成的幾何形狀形如多個(gè) 等腰直角三角形 ，每個(gè)三角形的直角頂點(diǎn)位于 0,10,20,... 等數(shù)位和突變的矩陣索引處 。

三角形內(nèi)的解雖然都滿(mǎn)足數(shù)位和要求，但由于機(jī)器人每步只能走一個(gè)單元格，而三角形間不一定是連通的，因此機(jī)器人不一定能到達(dá)，稱(chēng)之為 不可達(dá)解 ；同理，可到達(dá)的解稱(chēng)為 可達(dá)解 （本題求此解） 。

根據(jù)可達(dá)解的結(jié)構(gòu)和連通性，易推出機(jī)器人可 僅通過(guò)向右和向下移動(dòng)，訪(fǎng)問(wèn)所有可達(dá)解 。

• 三角形內(nèi)部： 全部連通，易證；

• 兩三角形連通處： 若某三角形內(nèi)的解為可達(dá)解，則必與其左邊或上邊的三角形連通（即相交），即機(jī)器人必可從左邊或上邊走進(jìn)此三角形。

方法一：深度優(yōu)先遍歷 DFS

• 深度優(yōu)先搜索： 可以理解為暴力法模擬機(jī)器人在矩陣中的所有路徑。DFS 通過(guò)遞歸，先朝一個(gè)方向搜到底，再回溯至上個(gè)節(jié)點(diǎn)，沿另一個(gè)方向搜索，以此類(lèi)推。

• 剪枝： 在搜索中，遇到數(shù)位和超出目標(biāo)值、此元素已訪(fǎng)問(wèn)，則應(yīng)立即返回，稱(chēng)之為 可行性剪枝 。

代碼如下：

復(fù)雜度分析

• 設(shè)矩陣行列數(shù)分別為 M, N。

• 時(shí)間復(fù)雜度 O(MN)： 最差情況下，機(jī)器人遍歷矩陣所有單元格，此時(shí)時(shí)間復(fù)雜度為 O(MN) 。

• 空間復(fù)雜度 O(MN)： 最差情況下，visited內(nèi)存儲(chǔ)矩陣所有單元格的索引，使用 O(MN) 的額外空間。

方法二：廣度優(yōu)先遍歷 BFS

• BFS/DFS ： 兩者目標(biāo)都是遍歷整個(gè)矩陣，不同點(diǎn)在于搜索順序不同。DFS 是朝一個(gè)方向走到底，再回退，以此類(lèi)推；BFS 則是按照“平推”的方式向前搜索。

• BFS 實(shí)現(xiàn)： 通常利用隊(duì)列實(shí)現(xiàn)廣度優(yōu)先遍歷。

代碼如下：

復(fù)雜度分析

• 設(shè)矩陣行列數(shù)分別為 M, N。

• 時(shí)間復(fù)雜度 O(MN)： 最差情況下，機(jī)器人遍歷矩陣所有單元格，此時(shí)時(shí)間復(fù)雜度為 O(MN)。

• 空間復(fù)雜度 O(MN)： 最差情況下，visited 內(nèi)存儲(chǔ)矩陣所有單元格的索引，使用 O(MN) 的額外空間。

END

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。