北京摇号网站维护,重庆网站设计开发,网站设计师要求,深圳建站公司专业公司地上有一个m行n列的方格#xff0c;一个机器人从坐标#xff08;0#xff0c;0#xff09;的格子开始移动#xff0c;它每次可以向上下左右移动一个格子#xff0c;但不能进入行坐标和列坐标的位数之和大于k的格子#xff0c;请问机器人能够到达多少个格子
#include 一个机器人从坐标00的格子开始移动它每次可以向上下左右移动一个格子但不能进入行坐标和列坐标的位数之和大于k的格子请问机器人能够到达多少个格子
#include vector // 包含vector头文件
#include queue // 包含queue头文件class Solution { // 定义解决方案类
private:int getSum(int x, int y) { // 计算坐标数位之和int sum 0; // 初始化和为0while (x 0) { // 处理x坐标sum x % 10; // 加上个位数x / 10; // 去掉个位数}while (y 0) { // 处理y坐标sum y % 10; // 加上个位数y / 10; // 去掉个位数}return sum; // 返回数位之和}public:int movingCount(int m, int n, int k) { // 计算可到达的格子数if (k 0) return 0; // 如果k小于0无法移动std::vectorstd::vectorbool visited(m, std::vectorbool(n, false)); // 记录已访问的格子std::queuestd::pairint, int q; // 用于BFS的队列int count 0; // 可到达的格子数q.push({0, 0}); // 起始点加入队列visited[0][0] true; // 标记起始点为已访问int dx[4] {-1, 1, 0, 0}; // x方向的移动int dy[4] {0, 0, -1, 1}; // y方向的移动while (!q.empty()) { // BFS主循环auto [x, y] q.front(); // 获取当前格子坐标q.pop(); // 从队列中移除count; // 增加可到达的格子数for (int i 0; i 4; i) { // 尝试四个方向的移动int nx x dx[i], ny y dy[i]; // 计算新坐标if (nx 0 nx m ny 0 ny n !visited[nx][ny] getSum(nx, ny) k) { // 检查新坐标是否有效q.push({nx, ny}); // 将新坐标加入队列visited[nx][ny] true; // 标记新坐标为已访问}}}return count; // 返回可到达的格子数}
};
这个实现使用了广度优先搜索BFS算法来解决问题。以下是主要的设计思路
我们定义了一个Solution类其中包含两个主要函数 getSum: 这是一个私有辅助函数用于计算坐标的数位之和。movingCount: 这是公共接口函数用于计算机器人能够到达的格子数量。在movingCount函数中 我们使用一个二维布尔数组visited来记录已经访问过的格子。使用一个队列q来进行BFS。从(0,0)开始将其加入队列并标记为已访问。使用一个while循环进行BFS每次从队列中取出一个格子然后尝试向四个方向移动。对于每个新的可能位置我们检查 是否在网格范围内是否已经被访问过数位之和是否不大于k如果满足所有条件我们将新位置加入队列并标记为已访问。每访问一个新的格子我们就将计数器加1。最后返回计数器的值即为机器人能够到达的格子数量。
这个算法的时间复杂度为O(mn)其中m和n分别是网格的行数和列数。空间复杂度也是O(mn)主要用于存储visited数组和BFS队列。
