剑指offer 13. 机器人的运动范围

2020年12月3日 周四天气晴 【不悲叹过去,不荒废现在,不惧怕未来】


我是菜鸡!

剑指offer 13. 机器人的运动范围
题目不难,类似于 LeetCode 79. 单词搜索(DFS+回溯) 这道题,只不过由于机器人是从左上角出发的,所以移动方向可以只考虑向右和向下(画下图就比较清楚了)。这道题我仿照单词搜索那题,硬是写了两个多小时,调了很久的bug,才勉强写出了下面可以通过的代码:

class Solution {
public:
	int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
	int movingCount(int m, int n, int k) {
		vector<vector<bool>> visited(m, vector<bool>(n, false));
		int maxCnt = 1;
		dfs(0, 0, k, visited, maxCnt);
		return maxCnt;
	}

	void dfs(int x, int y, int& k, vector<vector<bool>>& visited, int& cnt) {
		visited[x][y] = true;
		for (int i = 0; i < 4; ++i) {
			int new_x = x + dir[i][0];
			int new_y = y + dir[i][1];

			if (new_x < 0 || new_x >= visited.size() || new_y < 0 || new_y >= visited[0].size() || visited[new_x][new_y])
				continue;

			vector<int> new_coord;
			new_coord.emplace_back(new_x);
			new_coord.emplace_back(new_y);
			int sum = 0;
			for (int j = 0; j < 2; ++j) {
				while (new_coord[j] / 10 != 0) {
					sum += new_coord[j] % 10;
					new_coord[j] /= 10;
				}
				sum += new_coord[j];
			}
			if (sum <= k)
				dfs(new_x, new_y, k, visited, ++cnt);
		}
	}
};

剑指offer 13. 机器人的运动范围
时间感人。。。

怎么说的,还是不熟练吧,对回溯和递归掌握的不够透彻,以致于这么基础的题目写起来都很费劲儿,还有就是,拿到一个题目要先认真思考,思考清楚了再写代码,不要盲目下手,否则写出来的代码就会像上面那样,需要不断地修修补补,很臃肿

附上较为精简的代码:

class Solution {
public: 
	int movingCount(int m, int n, int k) {
        vector<vector<bool>> visited(m, vector<bool>(n, false));
		return dfs(visited, 0, 0, m, n, k);
	}

    //计算从位置(x,y)出发,能够到达多少格子
    int dfs(vector<vector<bool>>& visited, int x, int y, int& m, int& n, int& k){
        if(x>=m || y>=n || visited[x][y] || getSum(x) + getSum(y) > k) return 0;
        visited[x][y] = true;
        return 1 + dfs(visited, x+1, y, m, n, k) + dfs(visited, x, y+1, m, n, k);
    }

    // 获取val每位数的和
    int getSum(int val){
        int sum = 0;
        while(val/10 != 0){
            sum += val%10;
            val /= 10;
        }
        sum += val;
        return sum;
    }
};

参考文献
《剑指offer 第二版》
https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/comments/

上一篇:LeetCode200. 岛屿数量


下一篇:旅行商问题搜索求解