题目链接
LeetCode 面试题13. 机器人的运动范围[1]
题目描述
地上有一个 m 行 n 列的方格，从坐标 [0, 0] 到坐标 [m-1, n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于 k 的格子。例如，当 k 为 18 时，机器人能够进入方格 [35, 37] ，因为 3+5+3+7=18。但它不能进入方格 [35, 38]，因为 3+5+3+8=19。请问该机器人能够到达多少个格子？
示例1
输入：m = 2, n = 3, k = 1输出：3
示例2
输入：m = 3, n = 1, k = 0输出：1
说明：
1 <= n,m <= 1000 <= k <= 20
题解
这道题没有什么算法，比较简单，主要考察你的代码实现能力，这里我写了两个方法，一个 BFS，一个 DFS。
BFS
BFS 的思路就是用一个队列来保存即将要访问的结点，然后不断出队，将当前结点的四周的结点满足要求的入队。为了避免重复访问，可以用一个 vis 数组来标记已经访问过的结点位置。
DFS
DFS 思路就更加清晰简单了，对于一个结点来说，从它出发可以访问到的结点总数就等于从它四周的结点出发可以访问到的结点总数加一。同样需要用一个 vis 数组来标记已经访问过的结点位置。
代码
BFS（c++）
classSolution { public: intcountDigit(intx, inty) { intsum=0; while (x>0) { sum+=x%10; x/=10; } while (y>0) { sum+=y%10; y/=10; } returnsum; } intmovingCount(intm, intn, intk) { intdx[4] = {0, 0, 1, -1}; intdy[4] = {1, -1, 0, 0}; intres=0; vector<vector<int>>vis(m, vector<int>(n, 0)); queue<pair<int, int>>Q; Q.push({0, 0}); vis[0][0] =1; while (!Q.empty()) { pair<int, int>p=Q.front(); Q.pop(); res++; intnx=p.first, ny=p.second; for (inti=0; i<4; ++i) { intx=nx+dx[i], y=ny+dy[i]; if (0<=x&&x<m&&0<=y&&y<n&&!vis[x][y] &&countDigit(x, y) <=k) { vis[x][y] =1; Q.push({x, y}); } } } returnres; } };
DFS（c++）
classSolution { public: intdx[4] = {0, 0, 1, -1}; intdy[4] = {1, -1, 0, 0}; intcountDigit(intx, inty) { intsum=0; while (x>0) { sum+=x%10; x/=10; } while (y>0) { sum+=y%10; y/=10; } returnsum; } intdfs(intnx, intny, vector<vector<int>>&vis, int&m, int&n, int&k) { intres=1; for (inti=0; i<4; ++i) { intx=nx+dx[i], y=ny+dy[i]; if (0<=x&&x<m&&0<=y&&y<n&&!vis[x][y] &&countDigit(x, y) <=k) { vis[x][y] =1; res+=dfs(x, y, vis, m, n, k); } } returnres; } intmovingCount(intm, intn, intk) { vector<vector<int>>vis(m, vector<int>(n, 0)); vis[0][0] =1; intres=dfs(0, 0, vis, m, n, k); returnres; } };
参考资料
[1]
LeetCode 面试题13. 机器人的运动范围: https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
