文章目录
1. 题目2. 解题2.1 BFS2.2 DFS1. 题目
地上有一个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);}};