題目描述

地上有一個(gè)m行和n列的方格。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開始移動(dòng)，每一次只能向左，右，上，下四個(gè)方向移動(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è)格子？

解法一：

假設(shè)機(jī)器人當(dāng)前位置為（i，j），其可以去的位置為上（i-1，j）、下（i+1，j）、左（i，j-1）和右（i，j+1）。很明顯我們可以通過(guò)回溯法來(lái)求解，當(dāng)走到的點(diǎn)數(shù)位和超過(guò)k或者超出了邊界，則退回到上一個(gè)節(jié)點(diǎn)，繼續(xù)去遍歷別的節(jié)點(diǎn)。回溯法的重點(diǎn)是要建立一個(gè)標(biāo)志數(shù)組來(lái)標(biāo)記哪些點(diǎn)已經(jīng)被遍歷過(guò)。

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        boolean[] flag = new boolean[matrix.length];
        //初始化標(biāo)志矩陣
        for(int i = 0; i < flag.length; i++) {
            flag[i] = true;
        }
        //遍歷每一個(gè)格子，找到第一個(gè)存在要求路徑的格子時(shí)停止
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(hasNext(matrix, rows, cols, str, i, j, 0, flag)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean hasNext(char[] matrix, int rows, int cols, char[] str, int i, int j, int k, boolean[] flag) {
        int index = i * cols + j;
                //矩陣邊上格子的限定，i、j的限定要在index之前，否則index會(huì)溢出
        if(i >= rows || i < 0 || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == false) {
            return false;
        }
        if(k == str.length - 1) {
            return true;
        }
                //將進(jìn)入過(guò)的節(jié)點(diǎn)進(jìn)行標(biāo)記
        flag[index] = false;
        if(hasNext(matrix, rows, cols, str, i + 1, j, k + 1, flag) || 
           hasNext(matrix, rows, cols, str, i - 1, j, k + 1, flag) ||
           hasNext(matrix, rows, cols, str, i, j + 1, k + 1, flag) ||
           hasNext(matrix, rows, cols, str, i, j - 1, k + 1, flag)) {
            return true;
        }
                //若不符合條件，將標(biāo)記釋放，以便于回退后仍可進(jìn)入該格子
        flag[index] = true;
        return false;
    }
}

上面的程序先將標(biāo)志數(shù)組置為0，將遍歷到的但不滿足數(shù)位和約束的點(diǎn)置為1，遍歷到的滿足數(shù)位和約束條件的點(diǎn)置為2。最后統(tǒng)計(jì)置為2的點(diǎn)的個(gè)數(shù)即可。
由于java中形參傳遞的是引用的引用，直接操作的話會(huì)對(duì)原數(shù)據(jù)產(chǎn)生影響，所以遞歸回退的時(shí)候flag數(shù)組不會(huì)被重置。

解法二：

與解法一原理相同，但是每次遞歸時(shí)均記錄已符合條件的節(jié)點(diǎn)個(gè)數(shù)。

public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        int count = 0;
        int[] flag = new int[rows * cols];
        //初始化標(biāo)志數(shù)組
        for(int i = 0; i < flag.length; i++) {
            flag[i] = 0;
        }
        count = search(threshold, rows, cols, 0, 0, flag);
        return count;
        
    }
    public int search(int threshold, int rows, int cols, int i, int j, int[] flag) {
        int index = i * cols + j;
        int count = 0;
        if(i < 0 || i >= rows || j < 0 || j >= cols || flag[index] > 0) {
            return 0;
        }
        flag[index] = 1;
        /**由于滿足條件的點(diǎn)必定是連通的，所以可以通過(guò)連通點(diǎn)來(lái)遍歷得到所有滿足的點(diǎn)，對(duì)于不滿足的點(diǎn)，不再檢查其四周的點(diǎn)*/
        /**之所以必定連通是因?yàn)樗蟮臑闄C(jī)器人路徑上的點(diǎn)*/
        if(lessThanThreshold(threshold, i, j)) {
            count = 1 + search(threshold, rows, cols, i + 1, j, flag)
            + search(threshold, rows, cols, i - 1, j, flag)
            + search(threshold, rows, cols, i, j + 1, flag)
            + search(threshold, rows, cols, i, j - 1, flag);
        }
        return count;
    }
    /**判斷數(shù)位和是否小于thread*/
    public boolean lessThanThreshold(int threshold, int i, int j) {
        int count = 0;
        while(i % 10 != 0) {
            count += i % 10;
            i /= 10;
        }
        while(j % 10 != 0) {
            count += j % 10;
            j /= 10;
        }
        return count > threshold ? false : true;
    }
}