这是一个停车场寻找空余车位的问题
输入:
1 0 0 0 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 2
一是入口，二是空余车位，从一到二找最短路径，就是要找第一行的2，最后输出路径 ，1 0 0 0 2，输入不是固定的，但是1代表入口，2代表空余车位是固定的，c++，Python都可以，如果帮忙的话，感激不尽
需要代码，写全一点，本人学生，这个问题困扰我很长时间了
同学，如果光是求最短路，这就不用bfs，用曼哈顿距离就行（因为没有路障）。如果还要路径，用bfs求最短路，然后用一个pair存储上一个路径位置，最后将逆向路径存入stack类型，再输出即可。 另外，这类题去oj上看看题解就行，竞赛体系里，这都是很简单的。bfs
#include <iostream>
#include <queue>
#include <stack>
#include <cstring>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
PII pt[4] = { // 方向
{1,0}, {-1,0}, {0,1}, {0,-1}
};
const int N = 1021;
int n, ph[N][N];
struct node{
int zx,zy,zcnt; // (x,y) -- [cnt] :
};
PII pre[N][N];
// & 引用，因为有多个2，但是不知道哪个2是离一最近的，所以还要找那个2
int bfs(int sx, int sy, int &fastx, int &fasty) {
memset(pre,-1,sizeof(pre)); // 位置数组赋值-1
queue<node> q;
q.push({sx,sy,0});pre[sx][sy] = {0,0};
while(q.size()) {
auto t = q.front(); q.pop();
for(int i = 0; i < 4; ++i) {
int xx = t.zx + pt[i].x, yy = t.zy + pt[i].y, ccnt = t.zcnt;
if(xx < 0 || xx >= n || yy < 0 || yy >= n || pre[xx][yy].x != -1) continue;
q.push({xx,yy, ccnt+1});
pre[xx][yy] = {t.zx, t.zy};
if(ph[xx][yy] == 2) {
fastx = xx; fasty = yy;
return ccnt+1;
}
}
}
return -1;
}
int main() {
cin>>n;
int sx, sy;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
cin>>ph[i][j];
if(ph[i][j] == 1) sx = i, sy = j;
}
}
int fastx = 0, fasty = 0;
cout<<bfs(sx,sy,fastx, fasty)<<endl;
// 找路径
PII end = {fastx,fasty};
stack<PII> ansPath;
while(end.x != 0 || end.y != 0) {
ansPath.push(end);
end = pre[end.x][end.y];
if(end.x == 0 && end.y == 0) break;
}
// 输出
while(!ansPath.empty()) {
cout<<ansPath.top().x<<" "<<ansPath.top().y<<endl;
ansPath.pop();
}
}
#include<bits/stdc++.h>
using namespace std;
struct node {//结构体数组存队列的数据
int x,y,step;//x坐标，y坐标，以及步长（走了多少步）
}q[30];//迷宫有25个位置，多开一点
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};//增量数组，表示上下左右四个方向
int main() {
int a[5][5],i,j,n,m,head,tail,v[5][5]={0},tx,ty;
for(i=0;i<5;i++)
for(j=0;j<5;j++) {
cin>>a[i][j];//输入停车场
if(a[i][j]==1)//找到入口
n=i,m=j;//保存位置
}
q[1].x=n,q[1].y=m,q[1].step=0,v[n][m]=1;//将起点入队
head=0,tail=1;//初始化
while(head<tail) {//循环结束条件
head++;//指向待拓展的结点
for(i=0;i<4;i++) {//四个方向
tx=dx[i]+q[head].x,ty=dy[i]+q[head].y;//计算新结点的坐标
if(tx>=0&&tx<=4&&ty>=0&&ty<=4&&v[tx][ty]==0) {//如果新结点没越界且没走过
tail++;//为入队做准备
q[tail].x=tx,q[tail].y=ty,q[tail].step=q[head].step+1;//入队
v[tx][ty]=1;//标记走过
if(a[tx][ty]==2) {//找到空余车位
cout<<q[tail].step;//输出步长
return 0;//提前结束（小优化）
}
}
}
}
return 0;
}
我写的是广搜代码，望采纳(◕ᴗ◕✿)（C++）
我把很多解释写到代码里面了，看代码吧，python应该很容易理解
# 曼哈顿距离
def manhattan(x, y):
return abs(x[0] - y[0]) + abs(x[1] - y[1])
if __name__ == "__main__":
_map = [[1, 0, 0, 0, 2],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[2, 0, 0, 0, 2]]
start = None
end = []
for i in range(len(_map)):
for j in range(len(_map[0])):
if _map[i][j] == 1:
start = (i, j)
elif _map[i][j] == 2:
end.append((i, j))
# 计算start和每个end的曼哈顿距离
dis = [manhattan(start, end[i]) for i in range(len(end))]
# 曼哈顿距离最小的元素
min_dis = min(dis)
res = [end[i] for i in range(len(dis)) if dis[i] == min_dis]
print("车辆入口为：", start)
print("最短路径长度为：", min_dis)
print("最短距离的停车场位置有：", res)
# 最短路径的有太多条了，比如(0, 0)是入口， (1， 1)是最短路径，那么就有两条最短路径
# (0， 0)->(0, 1)->(1, 1)
# (0， 0)->(1, 0)->(1, 1)
# 所以单纯说最短路径，有太多了，我就直接给你求最短路径的长度了
from typing import Tuple
import math
import heapq
import pandas as pd
graph = {
"A": {"B":5,"C": 1},
"B": {"A": 5,"C":2,"D":1},
"C": {"A":1,"B":2,"D":4,"E": 8},
"D": {"B": 1, "C":4,"E": 3,"F": 6},
"E": {"C": 8,"D": 3,"X":7},
"F": {"D": 6,"Y":3},
"X": {},
"Y": {}
}
def init_distance(graph:dict, s:str)->dict:
distance = {s:0}
for vertex in graph:
if vertex != s:
distance[vertex] = math.inf
return distance
def dijkstra(graph:dict, s:str)->Tuple[dict,dict]:
pqueue = [] # 数组，模拟优先级队列
heapq.heappush(pqueue, (0, s)) # 每个结点保存 (边权值 顶点)
seen = set() # 保存已遍历的顶点
parent = {s:None} # 顶点-路径关系
distance = init_distance(graph, s) # 顶点-距离关系
while (len(pqueue) > 0): # while pqueue
pair = heapq.heappop(pqueue)
dist = pair[0]
vertex = pair[1]
seen.add(vertex)
nodes = graph[vertex].keys() # 顶点A所能达到的所有其他顶点
for w in nodes:
if w not in seen: # 该顶点还没有遇见过
if dist + graph[vertex][w] < distance[w]:
heapq.heappush(pqueue, (dist + graph[vertex][w], w))
parent[w] = vertex
distance[w] = dist + graph[vertex][w]
return parent, distance
parent, distance = dijkstra(graph, "A") # 调用算法
print( pd.DataFrame( # 以表格方式输出
[parent.values(),distance.values()], # 数据
index=["parent","distance"], # 行名
columns=parent.keys()) ) # 列名
'''
思路：
1. 如果两点路径不分叉，即对于路径 A->C->B->D->F->Y， 任意 C F 之间的最短路径即为他们之间的差值
详细path计算，通过parent数组逆推：patent[F]->D, parent[D]->B, parent[B]->C
2. 如果两点路径分叉，则需要查到公共的祖先结点 ↑→ F->Y
例如： A->C->B->D->E->X
求 X Y 最短路径，则需要先计算出公共的祖先结点 -》D
详细path计算：前缀：X..D + 后缀：D..Y
最短路径和计算： dist[X] - dist[comm] + dist[Y] - dist[comm]
'''
print("求最短路径: 输入起点，终点:")
while True:
start, end = input("->:").split()
if start in distance.keys() and end in distance.keys():
pre = [] # 前缀
path = [] # 计算路径,end
comm, cur = start, end # 如果没有分叉，comm公共祖先结点就是start，有分叉comm更新至公共结点
while cur and cur != start:
path.append(cur)
cur = parent[cur]
if start == cur: # 找到最短路径
path.append(cur)
path.reverse()
else:# 没有找到，start与end不在一条路径上，此时需要start也回溯找公共祖先结点
while comm not in path:
pre.append(comm)
comm = parent[comm]
# comm为公共祖先结点
path = pre + path[path.index(comm)::-1]
print("\tpath: ",path)
length = distance[end] - distance[comm] + distance[start] - distance[comm]
print("\tlength: ",length)
else:
print("输入有误，无此顶点信息")
import math
# 曼哈顿距离
def manhattan(x, y):
return abs(x[0] - y[0]) + abs(x[1] - y[1])
if __name__ == "__main__":
# _map = [[1, 0, 0, 0, 2],
# [0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0],
# [2, 0, 0, 0, 2]]
# ================= 自由输入 ===============
_map = []
while True:
m = input()
if m == "":
break
m = [int(i) for i in m.split()]
_map.append(m)
# =======================================
start = None
end = []
for i in range(len(_map)):
for j in range(len(_map[0])):
if _map[i][j] == 1:
start = (i, j)
elif _map[i][j] == 2:
end.append((i, j))
# 计算start和每个end的曼哈顿距离
dis = [manhattan(start, end[i]) for i in range(len(end))]
# 曼哈顿距离最小的元素
min_dis = min(dis)
res = [end[i] for i in range(len(dis)) if dis[i] == min_dis]
print("车辆入口为：", start)
print("最短路径长度为：", min_dis)
print("最短距离的停车场位置有：", res)
# 最短路径的有太多条了，比如(0, 0)是入口， (1， 1)是最短路径，那么就有两条最短路径
# (0， 0)->(0, 1)->(1, 1)
# (0， 0)->(1, 0)->(1, 1)
# 所以单纯说最短路径，有太多了，我就直接给你求最短路径的长度了
# ====================== 新增 =========================
# 从start到end的最短路径条数
for e in res:
m, n = abs(e[0] - start[0]) + 1, abs(e[1] - start[1]) + 1
print("从{}到{}的最短路径条数为：".format(start, e), math.comb(m + n - 2, m - 1))
'"
emmm....不是不给你输出，实在是太多了，给你求一下路径总条数吧，以你上面的_map为例，
如果没有(0, 4)那边的那个2，单纯(0, 0)到(4, 4)的最短路径就有70条，这输出。。。复杂度有点太高了
'"
同学，这个实在过于简单，不需要特别的复杂。学习一下Easy2D游戏引擎，把位置存入二维数组，在Easy2D坐标函数一键得知，我主页会持续更新这个专辑。但是如果你需要交作业的话……这种要插件什么的函数还是不建议用