剑指Offer - 面试题13. 机器人的运动范围（BFS/DFS）

文章目录

1. 题目

地上有一个m行n列的方格，从坐标[0,0]到坐标[m-1,n-1]。一个机器人从坐标[0, 0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 37]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：输入：m = 2, n = 3, k = 1输出：3示例 1：输入：m = 3, n = 1, k = 0输出：1提示：1 <= n,m <= 1000 <= k <= 20

来源：力扣（LeetCode）

链接：https://leetcode-/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 BFS

class Solution {public:int movingCount(int m, int n, int k) {vector<vector<bool>> visited(m, vector<bool>(n,false));vector<vector<int>> dir = {{-1,0},{1,0},{0,1},{0,-1}};queue<vector<int>> q;q.push({0,0});visited[0][0] = true;int count = 1, tpx, tpy, x, y, i;while(!q.empty()){tpx = q.front()[0];tpy = q.front()[1];q.pop();for(i = 0; i < 4; ++i){x = tpx+dir[i][0];y = tpy+dir[i][1];if(x>=0 && x<m && y>=0 && y<n && !visited[x][y] && valid(x,y,k)){q.push({x,y});visited[x][y] = true;count++;}} }return count;}bool valid(int x, int y, int &k){int sum = 0;while(x){sum += (x%10);x /= 10;}while(y){sum += (y%10);y /= 10;}return (sum<=k);}};

2.2 DFS

class Solution {vector<vector<int>> dir = {{-1,0},{1,0},{0,1},{0,-1}};public:int movingCount(int m, int n, int k) {vector<vector<bool>> visited(m, vector<bool>(n,false));int count = 1;visited[0][0] = true;dfs(0,0,count,visited,m,n,k);return count;}void dfs(int i, int j, int& count, vector<vector<bool>>& visited,int& m, int& n, int& k){int x, y;for(int a = 0; a < 4; ++a){x = i+dir[a][0];y = j+dir[a][1];if(x >=0 && x<m && y>=0 && y<n && !visited[x][y] && valid(x,y,k)){visited[x][y] = true;count++;dfs(x,y,count,visited,m,n,k);}}}bool valid(int x, int y, int &k){int sum = 0;while(x){sum += (x%10);x /= 10;}while(y){sum += (y%10);y /= 10;}return (sum<=k);}};