劍指Offer（六十六）：機器人的運動範圍(Java版)

描述

地上有一個 rows 行和 cols 列的方格。座標從 [0,0] 到 [rows-1,cols-1] 。一個機器人從座標 [0,0] 的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進入行座標和列座標的數位之和大於 threshold 的格子。例如，當 threshold 為 18 時，機器人能夠進入方格 [35,37] ，因為 3+5+3+7 = 18。但是，它不能進入方格 [35,38] ，因為 3+5+3+8 = 19 。請問該機器人能夠達到多少個格子？

資料範圍： 0 \le threshold \le 15 \0≤threshold≤15 ，1 \le rows,cols \le 100 \1≤rows,cols≤100進階：空間複雜度 O(nm) \O(nm) ，時間複雜度 O(nm) \O(nm)

示例1

輸入：1,2,3

返回值：3

示例2

輸入：0,1,3

返回值：1

示例3

輸入：10,1,100

返回值：29

說明：

[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 這29種，後面的[0,29],[0,30]以及[0,31]等等是無法到達的

示例4

輸入：5,10,10

返回值：21

第一種解法

使用dfs（深度優先搜尋）來解決，需要注意的一點。得防止重複的點二次計數。程式碼如下

int[][] arr = null;
int count = 0;
public int firstMovingCount(int threshold, int rows, int cols) {
    if(rows < 1 && cols < 1){
        return count;
    }
    if(threshold < 0){
        return count;
    }
    arr = new int[rows][cols];
    dsf(threshold,rows,cols,0,0);
    return count;
}

public void dsf(int threshold, int rows, int cols,int row,int col){
    if(row < 0 || row >= rows || col < 0 || col >= cols || arr[row][col] == 1){
        return;
    }
    if(check(row) + check(col) > threshold){
        return;
    }
    arr[row][col] = 1;
    count++;
    dsf(threshold,rows,cols,row+1,col);
    dsf(threshold,rows,cols,row-1,col);
    dsf(threshold,rows,cols,row,col+1);
    dsf(threshold,rows,cols,row,col-1);
}

int check(int num){
    int sum = 0;
    while (num > 0){
        sum += (num % 10);
        num = num /10;
    }
    return sum;
}

第二種解法

使用bfs(廣度優先搜尋)來解決。對於bfs的特性，採用佇列來實現是最好的，因為佇列是先進先出，離他最近的訪問完之後加入到佇列中，最先入隊的也是最先出隊的，程式碼如下

int[][] arr = null;
int count = 0;

int check(int num){
    int sum = 0;
    while (num > 0){
        sum += (num % 10);
        num = num /10;
    }
    return sum;
}

public int secondMovingCount(int threshold, int rows, int cols) {
    if(rows < 1 && cols < 1){
        return count;
    }
    if(threshold < 0){
        return count;
    }
    arr = new int[rows][cols];
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{0,0});
    while (!queue.isEmpty()){
        int[] poll = queue.poll();
        int i = poll[0];
        int j = poll[1];
        if(i >= rows || j >= cols || arr[i][j] == 1 || (check(i) + check(j) > threshold)){
            continue;
        }
        arr[i][j] = 1;
        count++;
        queue.add(new int[]{i+1,j});
        queue.add(new int[]{i,j+1});
    }
    return count;
}

分類： 數碼

時間： 2022-02-20