zkkKillua's Blog
0%

面试题13. 机器人的运动范围

发表于 更新于 分类于

框架

1
2
3
4
5
6
class Solution {
public:
    int movingCount(int m, int n, int k) {

    }
};

1. BFS

BFS到相邻节点，判断要求是否超过k。
时间O(mn)，空间由于需要一个网格记录是否访问过，也是O(mn). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int movingCount(int m, int n, int k) {
        int id[2] = {0, 1};
        int jd[2] = {1, 0};
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        queue<pair<int, int>> q;
        q.push(make_pair(0, 0));
        visited[0][0] = true;
        int ans = 1;

        while (!q.empty()) {
            pair<int, int> cur = q.front();
            q.pop();
            int i = cur.first, j = cur.second;
            for (int mv = 0; mv < 2; mv++) {
                if (i + id[mv] < m && j + jd[mv] < n && !visited[i + id[mv]][j + jd[mv]]) {
                    int sum = 0;
                    int loci = i + id[mv], locj = j + jd[mv];
                    while (loci > 0) {
                        sum += loci % 10;
                        loci /= 10;
                    }
                    while (locj > 0) {
                        sum += locj % 10;
                        locj /= 10;
                    }
                    if (sum <= k) {
                        q.push(make_pair(i + id[mv], j + jd[mv]));
                        ans++;
                    }
                    visited[i + id[mv]][j + jd[mv]] = true;
                }
            }
        }

        return ans;
    }
};