聲明

該系列文章僅僅展示個人的解題思路和分析過程，并非一定是優(yōu)質(zhì)題解，重要的是通過分析和解決問題能讓我們逐漸熟練和成長，從新手到大佬離不開一個磨練的過程，加油！

原題鏈接

機器人的運動范圍https://leetcode.cn/leetbook/read/illustration-of-algorithm/9h6vo2/

算法分析

? ? ? ? ?圖1是機器人移動范圍的網(wǎng)格，結(jié)合題目的描述，我們來確定變量和邏輯主體。

? ? ? ? （1）變量：設(shè)網(wǎng)格的行數(shù)為m，列數(shù)為n，移動限定值為k，設(shè)單元格坐標為(x,y)，[x]表示x的數(shù)位之和，[y]同理，可達坐標個數(shù)sum，已探索坐標列表list。

? ? ? ? （2）特殊描述：

????????①k是用于判斷移動是否合理的值，要求[x]+[y] <= k；

????????②數(shù)位之和：如數(shù)字45，[45]=4+5=9；

????????③移動方向分為上下左右，不可越界；

????????④起點為(0,0)，1 <= m <= 100，1 <= n <= 100，0 <= k <= 20；

? ? ? ? （3）求取[x]：

? ? ? ? ①x < 10，[x] = x；

????????②x >= 10，[x] = x - (x / 10) * 9；

? ? ? ? （4）越界判斷：

????????單元格坐標為(x,y)，x屬于[0,M-1]，y屬于[0,N-1]，若x或y均滿足指定取值范圍則表明未越界，反之則越界。

? ? ? ? （5）機器人移動：

????????傳入行數(shù)、列數(shù)、當前坐標、移動限定值、可達解個數(shù)、已訪問的坐標值列表。檢測當前坐標是否越界，若越界則return；檢測當前坐標數(shù)位和是否滿足條件，若不滿足則return；檢測當前坐標是否重復(fù)訪問，若重復(fù)訪問則return；三種情況均不滿足則將當前坐標添加至已訪問列表中，然后繼續(xù)嘗試往上下左右四個方向進行移動，重復(fù)上述過程。

? ? ? ? （6）定義一個坐標值數(shù)據(jù)結(jié)構(gòu)：

????????用于記錄橫縱坐標、比較坐標以及生成基于當前坐標指定方向的坐標值。

代碼示例（C#）

//主方法
public int MovingCount(int m, int n, int k)
{
    if (m <= 0 || n <= 0 || k < 0) return 0;
    int sum = 0;
    List<Vector2> list = new();
    Search(m, n, new(0, 0), k, ref sum, ref list);
    return sum;
}

//移動方向的枚舉值
private enum Direction
{
    unknown, left, right, up, down
}

//坐標值數(shù)據(jù)結(jié)構(gòu)
private struct Vector2
{
    public int x;//橫坐標
    public int y;//縱坐標

    public Vector2(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    //比較方法
    public bool CompareTo(Vector2 vector)
    {
        return x == vector.x && y == vector.y;
    }

    //生成基于當前坐標指定方向的坐標值
    public Vector2 Generate(Direction direction)
    {
        return direction switch
        {
            Direction.left => new Vector2(x - 1, y),
            Direction.right => new Vector2(x + 1, y),
            Direction.up => new Vector2(x, y + 1),
            Direction.down => new Vector2(x, y - 1),
            _ => new Vector2(x, y),
        };
    }
}

//坐標搜索方法
//參數(shù):行數(shù)、列數(shù)、坐標值、移動限定值、可達解個數(shù)、已訪問的坐標值列表
private void Search(int m, int n, Vector2 vector, int k, ref int sum, ref List<Vector2> list)
{
    //越界檢測
    if (vector.x < 0 || vector.x >= m || vector.y < 0 || vector.y >= n) return;
    //當前坐標的數(shù)位和檢測
    if (DigitalSum(vector.x) + DigitalSum(vector.y) > k) return;
    //重復(fù)訪問檢測
    if (list.Exists(vec => vec.CompareTo(vector))) return;
    list.Add(vector);
    sum++;
    //生成當前坐標的四個方向的坐標值
    Vector2[] vectors =
    {
        vector.Generate(Direction.left),
        vector.Generate(Direction.right),
        vector.Generate(Direction.up),
        vector.Generate(Direction.down)
    };
    //搜索四個方向的坐標
    Search(m, n, vectors[0], k, ref sum, ref list);
    Search(m, n, vectors[1], k, ref sum, ref list);
    Search(m, n, vectors[2], k, ref sum, ref list);
    Search(m, n, vectors[3], k, ref sum, ref list);
}

//計算指定值的數(shù)位和
private int DigitalSum(int val)
{
    if (val < 10) return val;
    return val - (val / 10) * 9;
}

算法解說

????????根據(jù)題目要求我們需要通過一個網(wǎng)格來模擬機器人的移動范圍，并且我們對機器人可移動的單元格進行了限定，我們從左至右和從上至下分別從小到大對坐標進行劃分，如此我們便可以唯一確定每一個單元格，如圖1所示。坐標除了用于記錄位置信息外我們還需要它提供一些特殊的方法，例如CompareTo和Generate，這兩個方法分別用于比較坐標和生成基于當前坐標指定方向的坐標，因此我們應(yīng)該把它單獨為一個類。

????????其次就是我們搜索機器人移動路徑的主要方法了，可以先嘗試模擬一下，我們從起始點出發(fā)，擁有四個可移動的方向，但是這就存在三個特殊情況，，所以我們需要對每個坐標進行判斷，第一需要考慮這個坐標是否越界，第二需要考慮這個坐標是否受到移動限定值的影響，第三需要考慮這個坐標是否已經(jīng)探索過，只有當以上三個情況均不滿足的時候，才應(yīng)該記錄為允許移動的坐標。

????????如何將算法分析轉(zhuǎn)換為代碼，依舊是確定兩個點，一是變量，二是邏輯主體，結(jié)合算法分析中的描述即可確定我們需要定義哪些變量以及邏輯主體是什么。文章來源地址http://www.zghlxwxcb.cn/news/detail-679688.html

到了這里，關(guān)于算法題——機器人的運動范圍的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！