地上有一个 mm 行和 nn 列的方格,横纵坐标范围分别是 0∼m−10∼m−1 和 0∼n−10∼n−1。
一个机器人从坐标 (0,0)(0,0) 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 kk 的格子。
请问该机器人能够达到多少个格子?
class Solution { public: int m, n; bool vis[55][55]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; typedef pair<int, int> PII; bool in (int x, int y) { return 0 <= x && x < m && 0 <= y && y < n; } int get (int x) { int ans = 0; while (x) { ans += x % 10; x /= 10; } return ans; } int movingCount(int k, int rows, int cols) { m = rows, n = cols; if (!m || !n) return 0; queue<PII> q; q.push({0, 0}); vis[0][0] = true; int ans = 0; while (q.size()) { auto now = q.front(); q.pop(); ans++; for (int i = 0; i < 4; i++) { int tx = now.first + dx[i]; int ty = now.second + dy[i]; if (in(tx, ty) && !vis[tx][ty] && get(tx) + get(ty) <= k) { vis[tx][ty] = true; q.push ({tx, ty}); } } } return ans; } };
标签:tx,ty,int,机器人,vis,运动,now,范围 From: https://www.cnblogs.com/leetothemoon/p/16980688.html