剑指OFFER----试题13. 机器人的运动范围
链接:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
思路:
dfs
代码:
class Solution { public: int get_single_sum(int x) { int s= 0; while (x) { s += x % 10; x /= 10; } return s; } int get_sum(pair<int, int> p) { return get_single_sum(p.first) + get_single_sum(p.second); } int movingCount(int m, int n, int k) { int res = 0; if (!m || !n) return 0; vector<vector<bool>> st(m, vector<bool>(n, false)); queue<pair<int, int>> q; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; q.push({0, 0}); while (q.size()) { auto t = q.front(); q.pop(); if (get_sum(t) > k || st[t.first][t.second]) continue; res++; st[t.first][t.second] = true; for (int i = 0; i < 4; ++i) { int x = t.first + dx[i], y = t.second + dy[i]; if (x >= 0 && x < m && y >= 0 && y < n) { q.push({x, y}); } } } return res; } };