習(xí)慣github pages風(fēng)格的請看我的另一篇博客

題目13：機器人的運動范圍

地上有個m行n列的方格。一個機器人從坐標(0,0)的格子開始移動，它每一次可以向左、右、上、下移動一格，但不能進入行坐標和列坐標的數(shù)位之和大于k的格子。

舉例說明

例如，當(dāng)k為18時，機器人能夠進入方格(35,37)，因為3+5+3+7=18。但它不能進入方格(35,38)，因為3+5+3+8=19。請問該機器人能夠達到多少格子？

思路

• 與12題類似，機器人從坐標(0,0)開始移動。當(dāng)它準備進入坐標為(i,j)的格子時，通過檢查坐標的數(shù)位和來判斷機器人是否能夠進入。如果機器人能夠進入坐標為(i,j)的格子，我們接著再判斷它能否進入四個相鄰的格子(i,j-1)、(i-1,j),(i,j+1)和(i+1,j)
• 不同的是準入條件的變化，方格中的內(nèi)容不再重要，僅需要方格的長和寬范圍即可
• 故“只停不退”，不用重置輔助數(shù)組對應(yīng)位置的布爾值

代碼實現(xiàn)

public class _13 {
    public static int movingCount(int threshold,int rows,int cols) {
        if(threshold<0||rows<1||cols<1) {
            return 0;
        }
        //初始化輔助數(shù)組
        boolean[] visitFlag=new boolean[rows*cols];
        for(int i=0;i<visitFlag.length;i++) {
                visitFlag[i]=false;
        }
        return movingCountCore(threshold,rows,cols,0,0,visitFlag);
    }

    private static int movingCountCore(
                  int threshold,int rows,int cols,int row,int col,boolean[] visitFlag) {
        int count=0;
        //達到限制的準入條件
        if(check(threshold,rows,cols,row,col,visitFlag)) {
           //標記為已經(jīng)進入，但不同于12題，之后不用回溯，所以只停不退
            visitFlag[row*cols+col]=true;
            count=1+movingCountCore(threshold, rows, cols, row-1, col, visitFlag)
                   +movingCountCore(threshold, rows, cols, row, col-1, visitFlag)
                   +movingCountCore(threshold, rows, cols, row+1, col, visitFlag)
                   +movingCountCore(threshold, rows, cols, row, col+1, visitFlag);
        }
        return count;
    }

    private static boolean check(
                int threshold,int rows,int cols,int row,int col,boolean[] visitFlag) {
        return col>=0 && col<cols && row>=0 && row<rows//沒過界
                && !visitFlag[row*cols+col]//沒來過
                && (getDigitSum(row)+getDigitSum(col)<=threshold);//數(shù)字符合題設(shè)
    }
    private static int getDigitSum(int number) {
        int sum=0;
        while(number>0) {
            sum=number%10;
            number/=10;
        }
        return sum;
    }
    public static void main(String[] args) {
        System.out.println(movingCount(3,3,3));//8,功能測試
        System.out.println(movingCount(0,1,1));//1,邊界測試
        System.out.println(movingCount(-3,3,3));//0,非法輸入測試
    }
}

輸出

image