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

Michael阿明

发布于 2020-07-13 16:03:40

2830

发布于 2020-07-13 16:03:40

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 <= 100
0 <= k <= 20

来源：力扣（LeetCode）链接：https://leetcode-cn.com/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);
    }
};