數組17--機器人的運動範圍

數組17--機器人的運動範圍-jz66

• ​​題目概述​​
• ​​解析&參考答案​​
• ​​注意事項​​
• ​​說明​​

題目概述

• 算法說明

  地上有一個m行和n列的方格。一個機器人從坐标0,0的格子開始移動，每一次隻能向左，右，上，下四個方向移動一格，但是不能進入行坐标和列坐标的數位之和大于k的格子。 例如，當k為18時，機器人能夠進入方格（35,37），因為3+5+3+7 = 18。但是，它不能進入方格（35,38），因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子？

  範圍:

  1 <= rows, cols<= 100

  0 <= threshold <= 20

• 測試用例

  案例1：

  輸入：5,10,10 輸出：21

  案例2：

  輸入：15,20,20 輸出：359

解析&參考答案

• 解析

  使用遞歸的方式擷取最終結果，起始地點為（0,0),在遞歸中傳回 1+遞歸目前點右邊點+遞歸目前點下面點，遞歸的時候需要使用一個map記錄目前點是否已經走過(走過則傳回0).

• 參考答案

vim jz66.go
package main

import "fmt"

func GetPositionSum(row, col int) int {
    sum := 0
    for row != 0 {
        sum += row % 10
        row = row / 10
    }
    for col != 0 {
        sum += col % 10
        col = col / 10
    }
    return sum
}

func MovingCountCore(threshold, r, c, rows, cols int, m map[int]int) int {
    if r >= rows || c >= cols { // 此處需要>=，否則會擴大範圍
        return 0
    }
    if m[r*cols+c] == 1 || GetPositionSum(r, c) > threshold {
        return 0
    }
    result := 0
    m[r*cols+c] = 1
    result = 1 + MovingCountCore(threshold, r+1, c, rows, cols, m) + MovingCountCore(threshold, r, c+1, rows, cols, m)
    return result
}

func MovingCount(threshold int, rows int, cols int) int {
    if rows == 0 || cols == 0 {
        return 0
    }
    m := make(map[int]int)
    result := MovingCountCore(threshold, 0, 0, rows, cols, m)
    return result
}

func main() {
    // threshold, rows, cols := 5, 10, 10
    threshold, rows, cols := 15, 20, 20
    result := MovingCount(threshold, rows, cols)
    fmt.Println(result)
}      

注意事項

1. to add

說明

1. 目前使用 go1.15.8
2. 參考​​牛客網--劍指offer​​ 标題中jzn(n為具體數字)代表牛客網劍指offer系列第n号題目，例如 jz01 代表牛客網劍指offer中01号題目。

• 筆者最近在學習 golang，是以趁機通過資料結構和算法來進一步熟悉下go語言
• 目前算法主要來源于劍指 offer，後續會進一步補充 LeetCode 上重要算法，以及一些經典算法
• 此處答案僅為參考，不一定是最優解，歡迎感興趣的讀者在評論區提供更優解