聲明

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

原題鏈接

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

算法分析

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

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

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

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

????????②數位之和：如數字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）機器人移動：

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

? ? ? ? （6）定義一個坐標值數據結構：

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

代碼示例（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
}//坐標值數據結構
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),};}
}//坐標搜索方法
//參數:行數、列數、坐標值、移動限定值、可達解個數、已訪問的坐標值列表
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;//當前坐標的數位和檢測if (DigitalSum(vector.x) + DigitalSum(vector.y) > k) return;//重復訪問檢測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);
}//計算指定值的數位和
private int DigitalSum(int val)
{if (val < 10) return val;return val - (val / 10) * 9;
}

算法解說

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

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

????????如何將算法分析轉換為代碼，依舊是確定兩個點，一是變量，二是邏輯主體，結合算法分析中的描述即可確定我們需要定義哪些變量以及邏輯主體是什么。