題目：地上有一個(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。請(qǐng)問(wèn)該機(jī)器人能夠到達(dá)多少個(gè)格子？ 題目地址

解題思路

這道題需要我們考慮兩個(gè)問(wèn)題

怎么走

這明顯是一個(gè)圖的遍歷問(wèn)題，我們可以使用深度DFS和廣度BFS。顯然深度優(yōu)先更適合這道題，我們可以使用回溯法借助深度優(yōu)先，往深處遍歷，發(fā)現(xiàn)不合適的點(diǎn)，回退一步，以回退點(diǎn)為起點(diǎn)，再向其他的方向深度優(yōu)先遍歷。

怎么判斷已經(jīng)走過(guò)

顯然我們需要一個(gè)外部存儲(chǔ)存儲(chǔ)已經(jīng)走的點(diǎn)，二維數(shù)組就很合適。坐標(biāo)的題類型都可以二外數(shù)組判斷是否重復(fù)。

代碼

public class Solution {
 
    public int movingCount(int threshold, int rows, int cols) {
        //二外數(shù)組，記錄是否已經(jīng)走過(guò)
        int flag[][] = new int[rows][cols];
        return walk(0, 0, rows, cols, flag, threshold);
    }
 
    private int walk(int i, int j, int rows, int cols, int[][] flag, int threshold) {
        if (i < 0 || i >= rows || j < 0 || j >= cols || numSum(i) + numSum(j)  > threshold || flag[i][j] == 1) return 0;    
        flag[i][j] = 1;
        return walk(i - 1, j, rows, cols, flag, threshold)
            + walk(i + 1, j, rows, cols, flag, threshold)
            + walk(i, j - 1, rows, cols, flag, threshold)
            + walk(i, j + 1, rows, cols, flag, threshold)
            + 1;
    }
    
    private int numSum(int i) {
        int sum = 0;
        do{
            sum += i%10;
        }while((i = i/10) > 0);
        return sum;
    }
}