技能培训网,优化方案数学2024电子版,一等一网站建设,网站建设栏目内容声明
该系列文章仅仅展示个人的解题思路和分析过程#xff0c;并非一定是优质题解#xff0c;重要的是通过分析和解决问题能让我们逐渐熟练和成长#xff0c;从新手到大佬离不开一个磨练的过程#xff0c;加油#xff01;
原题链接
机器人的运动范围https://leetcode.c…声明
该系列文章仅仅展示个人的解题思路和分析过程并非一定是优质题解重要的是通过分析和解决问题能让我们逐渐熟练和成长从新手到大佬离不开一个磨练的过程加油
原题链接
机器人的运动范围https://leetcode.cn/leetbook/read/illustration-of-algorithm/9h6vo2/
算法分析 图1 图1是机器人移动范围的网格结合题目的描述我们来确定变量和逻辑主体。 1变量设网格的行数为m列数为n移动限定值为k设单元格坐标为(x,y)[x]表示x的数位之和[y]同理可达坐标个数sum已探索坐标列表list。 2特殊描述 ①k是用于判断移动是否合理的值要求[x][y] k ②数位之和如数字45[45]459 ③移动方向分为上下左右不可越界 ④起点为(0,0)1 m 1001 n 1000 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;ListVector2 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 ListVector2 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这两个方法分别用于比较坐标和生成基于当前坐标指定方向的坐标因此我们应该把它单独为一个类。 其次就是我们搜索机器人移动路径的主要方法了可以先尝试模拟一下我们从起始点出发拥有四个可移动的方向但是这就存在三个特殊情况所以我们需要对每个坐标进行判断第一需要考虑这个坐标是否越界第二需要考虑这个坐标是否受到移动限定值的影响第三需要考虑这个坐标是否已经探索过只有当以上三个情况均不满足的时候才应该记录为允许移动的坐标。 如何将算法分析转换为代码依旧是确定两个点一是变量二是逻辑主体结合算法分析中的描述即可确定我们需要定义哪些变量以及逻辑主体是什么。
