class Solution {
public:
vector<vector<int>> bicycleYard(vector<int>& position, vector<vector<int>>& terrain, vector<vector<int>>& obstacle) {
}
};
LCP 45. 自行车炫技赛场
「力扣挑战赛」中 N*M 大小的自行车炫技赛场的场地由一片连绵起伏的上下坡组成，场地的高度值记录于二维数组 terrain 中，场地的减速值记录于二维数组 obstacle 中。
h1 且减速值为 o1 的位置到高度为 h2 且减速值为 o2 的相邻位置（上下左右四个方向），速度变化值为 h1-h2-o2（负值减速，正值增速）。选手初始位于坐标 position 处且初始速度为 1，请问选手可以刚好到其他哪些位置时速度依旧为 1。请以二维数组形式返回这些位置。若有多个位置则按行坐标升序排列，若有多个位置行坐标相同则按列坐标升序排列。
注意： 骑行过程中速度不能为零或负值
示例 1：
输入：
position = [0,0], terrain = [[0,0],[0,0]], obstacle = [[0,0],[0,0]]输出：
[[0,1],[1,0],[1,1]]解释： 由于当前场地属于平地，根据上面的规则，选手从
[0,0]的位置出发都能刚好在其他处的位置速度为 1。
示例 2：
输入：
position = [1,1], terrain = [[5,0],[0,6]], obstacle = [[0,6],[7,0]]输出：
[[0,1]]解释： 选手从
[1,1]处的位置出发，到[0,1]处的位置时恰好速度为 1。
提示：
n == terrain.length == obstacle.lengthm == terrain[i].length == obstacle[i].length1 <= n <= 1001 <= m <= 1000 <= terrain[i][j], obstacle[i][j] <= 100position.length == 20 <= position[0] < n0 <= position[1] < m原站题解
python3 解法, 执行用时: 52 ms, 内存消耗: 16.8 MB, 提交时间: 2023-09-17 11:42:03
class Solution:
def bicycleYard(self, pos: List[int], H: List[List[int]], O: List[List[int]]) -> List[List[int]]:
n, m = len(H), len(H[0])
q = [(pos[0], pos[1], 1)]
seen, res = set(q), []
while q:
x, y, v = q.pop()
for nx, ny in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
if 0 <= nx < n and 0 <= ny < m:
nv = v + H[x][y] - H[nx][ny] - O[nx][ny]
if nv <= 0 or (nx, ny, nv) in seen: continue
if nv == 1: res.append([nx, ny])
seen.add((nx, ny, nv))
q.append((nx, ny, nv))
return sorted(res)
python3 解法, 执行用时: 124 ms, 内存消耗: 18.6 MB, 提交时间: 2023-09-17 11:41:42
class Solution:
def bicycleYard(self, position: List[int], terrain: List[List[int]], obstacle: List[List[int]]) -> List[List[int]]:
Row = len(terrain)
Col = len(terrain[0])
res = set()
visited = [[set() for _ in range(Col)] for _ in range(Row)]
sr, sc = position[0], position[1]
q = collections.deque()
q.append((sr, sc, 1))
while q:
r, c, cur_speed = q.popleft()
if cur_speed in visited[r][c]:
continue
visited[r][c].add(cur_speed)
if (cur_speed == 1) and (r, c) != (position[0], position[1]):
res.add((r, c))
if len(res) == Row * Col:
break
for nr, nc in [(r-1,c), (r+1,c), (r,c-1), (r,c+1)]:
if 0 <= nr < Row and 0 <= nc < Col:
nxt_speed = terrain[r][c] - terrain[nr][nc] - obstacle[nr][nc] + cur_speed
if nxt_speed > 0:
q.append((nr, nc, nxt_speed))
return sorted(list(res))
java 解法, 执行用时: 11 ms, 内存消耗: 53.7 MB, 提交时间: 2023-09-17 11:41:17
class Solution {
Set<Integer> set;
int n, m;
int[][] move = new int[][]{
{0, 1},
{1, 0},
{-1, 0},
{0, -1},
};
int[][][] speed;
int nx, ny;
public int[][] bicycleYard(int[] pos, int[][] ter, int[][] obs) {
this.set = new HashSet<>();
this.n = ter.length;
this.m = ter[0].length;
this.speed = new int[n][m][110];
this.nx = pos[0];
this.ny = pos[1];
dfs(pos[0], pos[1], 1, ter, obs);
// 把set里面的数据提取出来
int[][] ans = new int[set.size()][2];
int id = 0;
for (int ni : set) {
ans[id][0] = ni / m;
ans[id][1] = ni % m;
id++;
}
// 按照题目规则进行排序
Arrays.sort(ans, (o1, o2) -> {
if (o1[0] == o2[0]) {
return o1[1] - o2[1];
}
return o1[0] - o2[0];
});
return ans;
}
public void dfs(int x, int y, int sp, int[][] ter, int[][] obs) {
// 剪枝
if (sp > 101 || sp <= 0 || speed[x][y][sp] == 1) return;
// set去重
if (sp == 1){
if (!(x == nx && y == ny)) {
set.add(x * m + y);
}
}
// 表示这个位置的这个速度已经到达过了
speed[x][y][sp] = 1;
// 模版形式的深搜
for (int[] ns : move) {
int dx = x + ns[0];
int dy = y + ns[1];
if (isOk(dx, dy)) continue;
dfs(dx, dy, sp + (ter[x][y] - ter[dx][dy] - obs[dx][dy]), ter, obs);
}
}
public boolean isOk(int x, int y) {
return x < 0 || x >= n || y < 0 || y >= m;
}
}
cpp 解法, 执行用时: 64 ms, 内存消耗: 42.4 MB, 提交时间: 2023-09-17 11:40:44
class Solution {
private:
static bool cmp(vector<int>& a, vector<int>& b) {
if(a[0] != b[0]) return a[0] < b[0];
else return a[1] < b[1];
}
public:
vector<vector<int>> bicycleYard(vector<int>& position, vector<vector<int>>& terrain, vector<vector<int>>& obstacle) {
vector<vector<int>> res;
//path 储存相邻节点坐标及其速度
vector<int> path(3,0);
//去重，不能定义为bool类型，用unordered_set 保存速度，因为经过不同轨迹到达到同一坐标位置的速度可能不一样，需要分开考虑
vector<vector<unordered_set<int>>> used(terrain.size(), vector<unordered_set<int>>(terrain[0].size()));
queue<vector<int>> que;
//相邻节点
vector<vector<int>> near = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
used[position[0]][position[1]].insert(1);
que.push({position[0], position[1], 1});
while(!que.empty()) {
int size = que.size();
for(int i = 0; i < size; i++) {
vector<int> pos = que.front();
que.pop();
int ii = pos[0];
int jj = pos[1];
int val = pos[2];
for(int k = 0; k < near.size(); k++) {
path[0] = ii + near[k][0];
path[1] = jj + near[k][1];
if(path[0] >= 0 && path[0] < terrain.size() && path[1] >= 0 && path[1] < terrain[0].size()) {
path[2] = val + terrain[ii][jj] - terrain[path[0]][path[1]] - obstacle[path[0]][path[1]];
//速度大于1才能继续骑行
if(path[2] >= 1) {
if(used[path[0]][path[1]].find(path[2]) == used[path[0]][path[1]].end()) {
//速度恰好等于1输出
if(path[2] == 1) res.push_back({path[0], path[1]});
que.push(path);
used[path[0]][path[1]].insert(path[2]);
}
}
}
}
}
}
sort(res.begin(), res.end(), cmp);
return res;
}
};
golang 解法, 执行用时: 80 ms, 内存消耗: 7.3 MB, 提交时间: 2023-09-17 11:40:19
/**
* 根据题目的数据范围，选手到任意位置的速度至多为 101，那么可以用 (x,y,speed) 表示状态，
* 从起点 (position[0],position[1],1) 开始跑 BFS。
* BFS 结束后，如果 (x,y,1) 被访问过，那么将 (x,y) 计入答案中。注意起点不能计入答案。
*/
var dir4 = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func bicycleYard(position []int, terrain, obstacle [][]int) (ans [][]int) {
n, m := len(terrain), len(terrain[0])
vis := make([][][102]bool, n)
for i := range vis {
vis[i] = make([][102]bool, m)
}
sx, sy := position[0], position[1]
vis[sx][sy][1] = true
type pair struct{ x, y, speed int }
q := []pair{{sx, sy, 1}}
for len(q) > 0 {
p := q[0]
q = q[1:]
x, y, speed := p.x, p.y, p.speed
for _, d := range dir4 {
if xx, yy := x+d.x, y+d.y; 0 <= xx && xx < n && 0 <= yy && yy < m {
s := speed + terrain[x][y] - terrain[xx][yy] - obstacle[xx][yy]
if s > 0 && !vis[xx][yy][s] {
vis[xx][yy][s] = true
q = append(q, pair{xx, yy, s})
}
}
}
}
vis[sx][sy][1] = false // 起点不计入答案
for i, row := range vis {
for j, b := range row {
if b[1] {
ans = append(ans, []int{i, j})
}
}
}
return
}