如何搭建公司网站,互联网巨头是哪几家,北京通信管理局网站备案,wordpress自动提取描述关键词今日份题目#xff1a;
地上有一个m行n列的方格#xff0c;从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动#xff0c;它每次可以向左、右、上、下移动一格#xff08;不能移动到方格外#xff09;#xff0c;也不能进入行坐标和列坐标的数位之…今日份题目
地上有一个m行n列的方格从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动它每次可以向左、右、上、下移动一格不能移动到方格外也不能进入行坐标和列坐标的数位之和大于k的格子。例如当k为18时机器人能够进入方格 [35, 37] 因为353718。但它不能进入方格 [35, 38]因为353819。请问该机器人能够到达多少个格子
示例1
输入m 2, n 3, k 1
输出3
示例2
输入m 3, n 1, k 0
输出1
提示 1 n,m 100 0 k 20
题目思路
由于机器人是从00开始走并不一定能走过所有格子甚至不一定能走到右下角所以其实是个搜索过程故使用广度优先遍历将满足条件坐标在格子内且位数和小于k的点坐标放入队列每次从队列中取出第一个点坐标判断向下向右两个点左边然后继续直到队列不为空。剪枝只考虑向下向右两个方向即可这是由本题规律得出的随着k的增大可行区域都是增加在右和下两个方向的 补充方向 代码
class Solution
{
public:int num(int x) //计算x的数位之和{string sto_string(x);//将int型数据转换成字符串类型int res0;for(int i0;is.length();i) {ress[i]-0;//计算各位之和}return res;}int movingCount(int m, int n, int k) {if(k0) return 1;queuepairint,int p;//向右和向下的方向数组int dx[2]{0,1};int dy[2]{1,0};int visited[200][200]{0};//用于标记是否到达过//从00开始p.push({0,0});visited[0][0]1;int ans1;//bfs广度优先遍历while(!p.empty()) {pairint,int xyp.front();p.pop();for(int i0;i2;i) //遍历两个方向{int txdx[i]xy.first;int tydy[i]xy.second;if(tx0||txm||ty0||tyn||visited[tx][ty]1||num(tx)num(ty)k) continue;//避免到方格外、被遍历过、数位之和大于kp.push({tx,ty});visited[tx][ty]1;ans;}}return ans;}
};提交结果 欢迎大家在评论区讨论如有不懂的代码部分欢迎在评论区留言
