
网站救助计划
1.为阅读体验,本站无任何广告,也无任何盈利方法,站长一直在用爱发电,现濒临倒闭,希望有能力的同学能帮忙分担服务器成本
2.捐助10元及以上同学,可添加站长微信lurenzhang888,备注捐助,网站倒闭后可联系站长领取本站pdf内容
3.若网站能存活下来,后续将会持续更新内容
题目描述
地上有一个 m 行 n 列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于 k 的格子。例如,当 k 为 18 时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为 3+5+3+8=19。请问该机器人能够到达多少个格子?
示例 1:
输入:m = 2, n = 3, k = 1
输出:3
示例 2:
输入:m = 3, n = 1, k = 0
输出:1
提示:
- 1 <= n,m <= 100
- 0 <= k <= 20
算法
(BFS) O(nm)
BFS 搜索所有可以到达的格子,初始状态将起点加入队列中,如果队列不为空,则弹出队头作为新的起点,如果当前点可以走,则枚举四个方向扩展下一层,将所有没有越界的点加入队列中,直到队列为空所有点就都被遍历完了。
哪些点可以走呢?
- 没有走过的点
- 当前点横纵坐标每位之和小于等于 k
时间复杂度
最坏情况下每个点都会被遍历一次,所以时间复杂度为 O(nm)。
空间复杂度
O(nm)
C++ 代码
class Solution {
public:
int get(int x) {
int res = 0;
while (x) {
res += x % 10;
x /= 10;
}
return res;
}
int movingCount(int m, int n, int k) {
vector<vector<bool>> st(m, vector<bool>(n, false));
int res = 0;
queue<pair<int, int>> q;
q.push({0, 0});
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while (q.size()) {
auto t = q.front();
q.pop();
int x = t.first, y = t.second;
if (st[x][y] || get(x) + get(y) > k) continue;
res ++ ;
st[x][y] = true;
for (int i = 0; i < 4; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= m || b < 0 || b >= n) continue;
q.push({a, b});
}
}
return res;
}
};
Java 代码
class Solution {
public int get(int x) {
int res = 0;
while (x > 0) {
res += x % 10;
x /= 10;
}
return res;
}
public int movingCount(int m, int n, int k) {
boolean[][] st = new boolean[m][n];
int res = 0;
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{0, 0});
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};
while (!q.isEmpty()) {
int[] t = q.poll();
int x = t[0], y = t[1];
if (x < 0 || x >= m || y < 0 || y >= n || st[x][y] || get(x) + get(y) > k) {
continue;
}
res ++ ;
st[x][y] = true;
for (int i = 0; i < 4; i ++ ) {
int a = x + dx[i], b = y + dy[i];
q.offer(new int[]{a, b});
}
}
return res;
}
}
Python 代码
class Solution:
def get(self, x: int) -> int:
res = 0
while x > 0:
res += x % 10
x //= 10
return res
def movingCount(self, m: int, n: int, k: int) -> int:
st = [[False] * n for _ in range(m)]
res = 0
q = deque([(0, 0)])
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
while q:
x, y = q.popleft()
if x < 0 or x >= m or y < 0 or y >= n or st[x][y] or self.get(x) + self.get(y) > k:
continue
res += 1
st[x][y] = True
for i in range(4):
a, b = x + dx[i], y + dy[i]
q.append((a, b))
return res
本文由读者提供,Github地址:https://github.com/tonngw
点击面试手册,获取本站面试手册PDF完整版