20106: 走山路
bfs + heap, Dijkstra, http://cs101.openjudge.cn/practice/20106/
某同学在一处山地里，地面起伏很大，他想从一个地方走到另一个地方，并且希望能尽量走平路。 现有一个m*n的地形图，图上是数字代表该位置的高度，"#"代表该位置不可以经过。 该同学每一次只能向上下左右移动，每次移动消耗的体力为移动前后该同学所处高度的差的绝对值。现在给出该同学出发的地点和目的地，需要你求出他最少要消耗多少体力。
输入
第一行是m,n,p，m是行数，n是列数，p是测试数据组数 接下来m行是地形图 再接下来n行每行前两个数是出发点坐标（前面是行，后面是列），后面两个数是目的地坐标（前面是行，后面是列）（出发点、目的地可以是任何地方，出发点和目的地如果有一个或两个在"#"处，则将被认为是无法达到目的地）
输出
n行，每一行为对应的所需最小体力，若无法达到，则输出"NO"
样例输入
4 5 3
0 0 0 0 0
0 1 1 2 3
# 1 0 0 0
0 # 0 0 0
0 0 3 4
1 0 1 4
3 4 3 0样例输出
2
3
NO
解释：
第一组：从左上角到右下角，要上1再下来，所需体力为2
第二组：一直往右走，高度从0变为1，再变为2，再变为3，消耗体力为3
第三组：左下角周围都是"#"，不可以经过，因此到不了来源: cs101-2019 张翔宇
Dijkstra 算法的本质是贪心策略，每次扩展的是当前路径代价最小的节点，要维护该贪心性。
python
import heapq #260ms
def find_min_cost_path(n, m, mat, queries):
directions = [(1, 0), (0, 1), (0, -1), (-1, 0)]
results = []
for x, y, xx, yy in queries:
if mat[x][y] == '#' or mat[xx][yy] == '#':
results.append("NO")
continue
dist = {(x, y): 0} # Distance dictionary to keep track of minimum cost to each node
heap = [(0, x, y)] # Priority queue: (cost, row, col)
found = False
while heap:
cost, i, j = heapq.heappop(heap)
# If the target is reached, record the result and exit the loop
if (i, j) == (xx, yy):
results.append(cost)
found = True
break
# Explore all possible moves
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < n and 0 <= nj < m and mat[ni][nj] != '#':
new_cost = cost + abs(int(mat[ni][nj]) - int(mat[i][j]))
# Update the cost if it's lower than any previously recorded cost
if (ni, nj) not in dist or new_cost < dist[(ni, nj)]:
dist[(ni, nj)] = new_cost
heapq.heappush(heap, (new_cost, ni, nj))
if not found:
results.append("NO")
return results
# Input processing
n, m, p = map(int, input().split())
mat = [input().split() for _ in range(n)]
queries = [tuple(map(int, input().split())) for _ in range(p)]
# Solve the problem and output results
answers = find_min_cost_path(n, m, mat, queries)
print("\n".join(map(str, answers)))这里学会了如何优化进行剪枝，heapq是最小堆，只要是非负权值的最短路径问题，就可以使用Dijkstra算法，不断用全局中最小的进行更新，把含权值的最短路径问题给推出来。贪心思想：Dijkstra 的核心是贪心扩展——每次优先访问当前代价最小的节点，并通过该节点更新其他节点的代价，从而保证扩展的节点顺序是代价从小到大的。剪枝的具体实现
1. 劣路径的剪枝：剪枝可以避免无效的路径计算，从而显著减少搜索空间。
python
if effort > min_effort[x][y]:
continue • 如果当前路径的累计代价 effort 已经大于记录的最优代价 min_effort[x][y]，则说明这条路径已经不是最优的，继续扩展它是没有意义的，直接跳过（剪枝）。剪枝原理：节点的最优代价是按贪心原则逐步更新的。一旦 effort > min_effort[x][y]，说明当前路径已被更优的路径取代。
2. 路径更新的剪枝：
python
if total_effort < min_effort[nx][ny]:
min_effort[nx][ny] = total_effort
heapq.heappush(pq, (total_effort, nx, ny)) • 只有当新路径的累计代价 total_effort 小于已知的代价 min_effort[nx] [ny] 时，才更新邻居节点的代价并加入堆中。 • 如果新路径的代价不优于当前最优代价，则直接忽略，避免对无意义的路径进行扩展。
3. 起点或终点为阻碍的剪枝：如果起点或终点是不可通行的（#），直接输出 NO，不再进行路径搜索。
python
if terrain[sx][sy] == '#' or terrain[ex][ey] == '#':
results.append('NO')使用 heapq 最小堆管理优先级队列，使得插入和取出操作的时间复杂度为 O(log n) ，保证算法整体高效。
python
import heapq
def min_effort_dijkstra(terrain, m, n, start, end):
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
pq = [(0, start[0], start[1])]
min_effort = [[float('inf')] * n for _ in range(m)]
min_effort[start[0]][start[1]] = 0
while pq:
effort, x, y = heapq.heappop(pq)
if (x, y) == end:
return effort
if effort > min_effort[x][y]:
continue
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and terrain[nx][ny] != '#':
next_effort = abs(int(terrain[nx][ny]) - int(terrain[x][y]))
total_effort = effort + next_effort
if total_effort < min_effort[nx][ny]:
min_effort[nx][ny] = total_effort
heapq.heappush(pq, (total_effort, nx, ny))
return 'NO'
m, n, p = map(int, input().split())
terrain = [input().strip().split() for _ in range(m)]
results = []
for _ in range(p):
sx, sy, ex, ey = map(int, input().split())
if terrain[sx][sy] == '#' or terrain[ex][ey] == '#':
results.append('NO')
else:
results.append(min_effort_dijkstra(terrain, m, n, (sx, sy), (ex, ey)))
print("\n".join(map(str, results)))python
# 23 苏王捷 1681ms
import heapq
m, n, p = map(int, input().split())
martix = [list(input().split())for i in range(m)]
dir = [(-1, 0), (1, 0), (0, 1), (0, -1)]
for _ in range(p):
sx, sy, ex, ey = map(int, input().split())
if martix[sx][sy] == "#" or martix[ex][ey] == "#":
print("NO")
continue
in_queue, heap, ans = set(), [], []
heapq.heappush(heap, (0, sx, sy))
in_queue.add((sx, sy, -1))
while heap:
tire, x, y = heapq.heappop(heap)
if x == ex and y == ey:
ans.append(tire)
for i in range(4):
dx, dy = dir[i]
x1, y1 = dx+x, dy+y
if 0 <= x1 < m and 0 <= y1 < n and martix[x1][y1] != "#" and (x1, y1, i) not in in_queue:
t1 = tire+abs(int(martix[x][y])-int(martix[x1][y1]))
heapq.heappush(heap, (t1, x1, y1))
in_queue.add((x1, y1, i))
print(min(ans) if ans else "NO")python
# 胡睿诚 174ms
import heapq
m, n, p = map(int, input().split())
info = []
for _ in range(m):
info.append(list(input().split()))
directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
def dijkstra(start_r, start_c, end_r, end_c):
pos = []
dist = [[float('inf')] * n for _ in range(m)]
if info[start_r][start_c] == '#':
return 'NO'
dist[start_r][start_c] = 0
heapq.heappush(pos, (0, start_r, start_c))
while pos:
d, r, c = heapq.heappop(pos)
if r == end_r and c == end_c:
return d
h = int(info[r][c])
for dr, dc in directions:
nr = r + dr
nc = c + dc
if 0 <= nr < m and 0 <= nc < n and info[nr][nc] != '#':
if dist[nr][nc] > d + abs(int(info[nr][nc]) - h):
dist[nr][nc] = d + abs(int(info[nr][nc]) - h)
heapq.heappush(pos, (dist[nr][nc], nr, nc))
return 'NO'
for _ in range(p):
x, y, z, w = map(int, input().split())
print(dijkstra(x, y,z,w))python
from collections import deque # 1178ms
def bfs(x, y):
# 定义方向的偏移量
directions = [(0, -1), (0, 1), (1, 0), (-1, 0)]
# 初始化队列，将起点加入队列
queue = deque([(x, y)])
# 初始化距离字典，将起点的距离设为0，其他节点设为无穷大
distances = {(x, y): 0} # 不用heap，则需要用二维表
while queue:
# 弹出队列中的节点
current_x, current_y = queue.popleft()
# 遍历四个方向上的相邻节点
for dx, dy in directions:
new_x, new_y = current_x + dx, current_y + dy
# 判断新节点是否在合法范围内
if 0 <= new_x < m and 0 <= new_y < n:
# 判断新节点是否为墙
if d[new_x][new_y] != '#':
# 计算新节点的距离
new_distance = distances[(current_x, current_y)] + abs(int(d[new_x][new_y]) - int(d[current_x][current_y]))
# 如果新节点的距离小于已记录的距离，则更新距离字典和队列
if (new_x, new_y) not in distances or new_distance < distances[(new_x, new_y)]:
distances[(new_x, new_y)] = new_distance
queue.append((new_x, new_y))
return distances
# 读取输入
m, n, p = map(int, input().split())
d = []
for _ in range(m):
row = input().split()
d.append(row)
for _ in range(p):
# 读取起点和终点坐标
x1, y1, x2, y2 = map(int, input().split())
# 判断起点和终点是否为墙
if d[x1][y1] == '#' or d[x2][y2] == '#':
print('NO')
continue
# 使用BFS计算最短距离
distances = bfs(x1, y1)
# 输出结果，如果终点在距离字典中，则输出对应的最短距离，否则输出'NO'
if (x2, y2) in distances:
print(distances[(x2, y2)])
else:
print('NO')注意 line 11: visited.add(..)，在heappop之后，保证最优的才入v。加入剪枝，时间可以缩小到201ms。
heappop的时候，才能入visited，这样才能保证最短的优先访问，否则最短路径可能加不进inq。
python
# 23 蒋子轩 211ms
from heapq import heappop, heappush
def bfs(x1, y1):
q = [(0, x1, y1)]
visited = set()
while q:
t, x, y = heappop(q)
if (x, y) in visited: # 剪枝，因为heappush会导致重复入队
continue
visited.add((x, y))
if x == x2 and y == y2:
return t
for dx, dy in dir:
nx, ny = x+dx, y+dy
if 0 <= nx < m and 0 <= ny < n and \
ma[nx][ny] != '#' and (nx, ny) not in visited:
nt = t+abs(int(ma[nx][ny])-int(ma[x][y]))
heappush(q, (nt, nx, ny))
return 'NO'
m, n, p = map(int, input().split())
ma = [list(input().split()) for _ in range(m)]
dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for _ in range(p):
x1, y1, x2, y2 = map(int, input().split())
if ma[x1][y1] == '#' or ma[x2][y2] == '#':
print('NO')
continue
print(bfs(x1, y1))C++
c++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
#include <cstdlib>
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> piii; // (cost, (row, col))
int main() {
int m, n, p;
cin >> m >> n >> p;
vector<vector<string>> mat(m, vector<string>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
cin >> mat[i][j];
}
}
vector<vector<int>> queries(p, vector<int>(4));
for (int i = 0; i < p; ++i) {
for (int j = 0; j < 4; ++j) {
cin >> queries[i][j];
}
}
const int directions[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
vector<string> results;
auto isValid = [&](int x, int y) {
return x >= 0 && x < m && y >= 0 && y < n && mat[x][y] != "#";
};
for (const auto &query : queries) {
int sx = query[0], sy = query[1];
int ex = query[2], ey = query[3];
if (!isValid(sx, sy) || !isValid(ex, ey)) {
results.push_back("NO");
continue;
}
priority_queue<piii, vector<piii>, greater<piii>> pq;
pq.push({0, {sx, sy}});
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
dist[sx][sy] = 0;
bool found = false;
while (!pq.empty()) {
auto [cost, pos] = pq.top();
pq.pop();
int i = pos.first, j = pos.second;
if (i == ex && j == ey) {
results.push_back(to_string(cost));
found = true;
break;
}
for (const auto& dir : directions) {
int ni = i + dir[0], nj = j + dir[1];
if (isValid(ni, nj)) {
int current_height = stoi(mat[i][j]);
int new_height = stoi(mat[ni][nj]);
int new_cost = cost + abs(current_height - new_height);
if (new_cost < dist[ni][nj]) {
dist[ni][nj] = new_cost;
pq.push({new_cost, {ni, nj}});
}
}
}
}
if (!found) {
results.push_back("NO");
}
}
for (const string &result : results) {
cout << result << endl;
}
return 0;
}【昂奕,化学与分子工程学院】
Dijkstra算法
- 读作/'daikstrə/,不是dijiekestra...
- 这个算法用于以下情景:一个加权的图(图的每条连线都有一个权重),要求A到B点权重代数和的最小值.
- 例如,几座城市之间修了一些路,每条路有一个长度,要求A城到B城最短的路是多长.
- 对于一般的图,都是如下做法:
- 构建邻接表(每个节点跟其他哪些节点连在一起,列一张表).
- 构建小顶堆q存储即将遍历的点
- 一边遍历一边探路一边更新最小距离(就是bfs)
- 看起来很抽象.直接上代码:
python
import heapq
def dijkstra(n, edges, s, t):
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))#构建邻接表
pq = [(0, s)] # (distance, node)
visited = set()
distances = [float('inf')] * n
distances[s] = 0
while pq:#遍历节点
dist, node = heapq.heappop(pq)
if node == t:return dist
if node in visited:
continue
visited.add(node)
for neighbor, weight in graph[node]:#走到一个节点-->探路边上的邻居
if neighbor not in visited:
new_dist = dist + weight #更新距离
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return -1这段代码更抽象了,也不够贴近生活实际.
在CS101中,我们见到的更多是基于矩阵的Dijkstra算法,因此我们来看看,如果遍历的是矩阵这种特殊的图,Dijkstra算法长什么样.
Dijkstra的本质是bfs,所以我们拿bfs的代码简单改一下就好了.以下是将一个普通bfs修改为Dijkstra的过程:(注:以下的权重和/权值和就比如说走山路那题的体力消耗量)
- 把函数名从bfs改成Dijkstra(确信)
- 用小顶堆代替原先的队列q,q中的元素为(w,x,y)元组,其中w是权值和,x,y是坐标.这样每次访问的都是q中权值和最小的点.(实际上这叫优先队列)每次都访问权值和最小的点,使得第一次到终点时的权值和就是全局最小的权值和,也就是第一次到终点的时候就可以直接break而不需要再从其他路径到终点来更新最小权值和. 注意:heapq的元素如果是元组,会依次按元组中第一,第二...个元素的大小作为该元组的大小比较的依据.所以为了让q按权重和排序,q中的点应表示为
(w,x,y),其中w=weight[x][y],是该点到起点的最小权重和 - 建立一个与mat一样大的weight矩阵存储起点到每个点的最小权重和,每个点初值赋为无穷大,除了起点是0(权值和既需要存在这个矩阵里,也要存在q中的元组里,两个地方都需要用到这个权值和)
- 开始bfs,
while q...这段不变 - 探路,
for dx,dy in d... 这段,入q条件改成:nx,ny在矩阵范围内,起点到nx,ny的权重和小于weight[nx][ny](之前的路径走出的起点到nx,ny的权重和) - 在入堆的同时更新
weight[nx][ny]
代码如下:
python
import heapq
def dijkstra(s,mat,e):#s,e分别是起点和终点.起点s=(0,x0,y0),终点e=(xe,ye).
MAXN=float('inf')
weight=[[MAXN]*len(mat[0]) for _ in range(len(mat))]
q=[s]
weight[s[1]][s[2]]=0
d=[(-1,0),(1,0),(0,-1),(0,1)]
#开始bfs
while q:
w,x,y=heapq.heappop(q)
#先处理到终点的情况
if (x,y)==e:
return weight[x][y]
#然后探路
for dx,dy in d:
nx,ny=x+dx,y+dy
if 0<=nx<len(mat) and 0<=ny<len(mat[0]):#不用not in visited
new_w=weight[x][y]+______#这段填上点(x,y)到(nx,ny)的权重,如走山路就是abs(int(mat[nx][ny])-int(mat[x][y]))即(x,y)和(nx,ny)的高度差绝对值
if new_w<weight[nx][ny]:
weight[nx][ny]=new_w
heapq.heappush(q,(new_w,nx,ny))
return -1(上面这些能讲明白吗...www)