- C++
最短路径-搜索
- 2025-1-19 13:37:55 @
#include<iostream>
#include<cstdio>
using namespace std;
struct Point
{
int x, y;
};
Point start , end,path[N][N];
void showPath(int x, int y)
{
if(x == start.x && y == start.y)
{
cout << "()"...
return;
}
showPath(path[x][y]...);
cout << "->(x, y)";
}
void bfs()
{
queue<Point> mq;
mq.push(start);
while(mq.size())
{
Point p = mq.front();
mq.pop();
if(.....)
{
// 是否到达终点
}
for(int i = 0; i < 4; i ++)
{
int cx = , cy= ;
if(...) //在范围内
//
path[cx][cy] = p;
mq.push({cx, cy});
}
}
}
int main(void)
{
// 输入
bfs();
showPath(end.x, end.y);
return 0;
}
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 155;
int n, m, f;
int a[N][N];
bool vis[N][N];
int sx, sy, ex, ey;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
struct Point
{
int x, y;
};
Point myPath[N][N];
void initInput(void)
{
ios::sync_with_stdio(0);
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
cin >> sx >> sy >> ex >> ey;
}
void showPath(Point t)
{
f = 1;
if(t.x == sx && t.y == sy)
{
cout << "(" << t.x << "," << t.y << ")";
return;
}
showPath(myPath[t.x][t.y]);
cout << "->(" << t.x << "," << t.y << ")";
}
void handle(void)
{
queue<Point> mq;
myPath[sx][sy] = {sx, sy};
mq.push({sx, sy});
while(mq.size())
{
Point t = mq.front();
mq.pop();
if(t.x == ex && t.y == ey)
{
showPath({ex, ey});
cout << endl;
return;
}
for(int i = 0; i < 4; i++)
{
int cx = t.x + dx[i], cy = t.y + dy[i];
if(cx < 1 || cy < 1 || cx > n || cy > m) continue;
if(a[cx][cy] == 1) continue;
if(vis[cx][cy]) continue;
vis[cx][cy] = 1;
myPath[cx][cy] = t;
mq.push({cx, cy});
}
}
if(f==0)
cout << "no way" << endl;
}
int main(void)
{
initInput();
handle();
return 0;
}
0 条评论
目前还没有评论...