机器人的运动范围

ryluo 2020-06-23 09:11:54

地上有一个 m 行和 n 列的方格,横纵坐标范围分别是 0∼m−10∼m−1 和 0∼n−1。

一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k的格子。

请问该机器人能够达到多少个格子?

样例1

输入:k=7, m=4, n=5

输出:20

样例2

输入:k=18, m=40, n=40

输出:1484

解释:当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。
      但是,它不能进入方格(35,38),因为3+5+3+8 = 19。

注意:

  1. 0<=m<=50
  2. 0<=n<=50
  3. 0<=k<=100

分析:

深度优先搜索:需要使用递归,并且涉及到状态或者子问题的概念

假设当前状态为(i, j),那么问题就变成,机器人从(i,j)出发最多可以达到多少个格子

根据机器人的运动规则,子问题可以分解为,机器人分别到达(i, j-1), (i, j+1), (i-1,j), (i+1, j)位置(即上下左右)的格子数总和,再加1,因为这里需要加上起始位置。

注意:对于矩阵的搜索需要定义一个二维数组记录元素是否被访问过,如果被访问过就返回0

dfs优化: 每次搜索都会形成一个连通域,所以每次只需要向右及向下即可

从左上角位置(0,0)处开始,

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        //dfs
        // 定义一个二维数组标记是否被访问过
        vector<vector<bool>> visited(rows, vector<bool>(cols));

        return dfs(0, 0, threshold, rows, cols, visited);
    }

    int dfs(int x, int y, int k, int n, int m, vector<vector<bool>>& visited){
        if(x < 0 || x >= n || y < 0 || y >= m || getSum(x) + getSum(y) > k || visited[x][y]==true){
            return 0;
        }

        visited[x][y] = true;

        // return dfs(x - 1, y, k, n, m, visited) + dfs(x + 1, y, k, n, m, visited) + 
        //       dfs(x, y - 1, k, n, m, visited) + dfs(x, y + 1, k, n, m, visited) + 1;

        return dfs(x + 1, y, k, n, m, visited) + dfs(x, y + 1, k, n, m, visited) + 1;
    }

    int getSum(int x){
        int res = 0;
        while(x){
            res += x % 10;
            x /= 10;
        }
        return res;
    }

};

广度优先搜索:

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        // bfs
        // 定义一个二维数组标记是否被访问过
        if(!rows || !cols) return 0;

        vector<vector<bool>> visited(rows, vector<bool>(cols));
        queue<pair<int, int>> q; // 定义一个队列用来存放当前层需要处理的元素
        q.push({0, 0});  // 初始的时候将起始点压入队列
        int res = 0;

        while(q.size()){
            auto p = q.front();  // 取出队列中的元素
            q.pop();

            int i = p.first, j = p.second;
            if(getSum(i) + getSum(j) > threshold || visited[i][j]) continue;  //判断当前元素是否满足条件

            visited[i][j] = true; // 对访问过的元素进行标记
            res++;

            int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
            for(int k = 0; k < 4; k++){
                int a = i + dx[k], b = j + dy[k];
                if (a >= 0 && a < rows && b >=0 && b < cols) q.push({a, b});  // 将满足边界条件的元素压入队列
            }

        }

        return res;
    }

    int getSum(int x){
        int res = 0;
        while(x){
            res += x % 10;
            x /= 10;
        }
        return res;
    }
};