输入格式
给定一个大小为n * m的迷宫，求出从起点到终点的最小步数，只能上下左右四个方向走（若起点无法到达终点则输出-1）【*代表通道、#代表墙壁】
输出格式
一个整数，代表从起点到终点的最小步数。
样例
Input 1
5 6
***#
####
*###
##*#
1 1 5 3
Output 1
6
样例解释
约定：
0<n,m<50
数据范围
0<n,m<50
广搜即可
模版给你（不是AC代码！！！）：
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
// 定义节点结构体，包含位置和步数
struct Node {
int x, y; // 节点在网格中的位置
int step; // 到达该节点所需的步数
};
// 方向数组，用于上下左右移动
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
// 检查节点是否合法（在网格内且不是障碍物）
bool isValid(int x, int y, int n, int m, char grid[n][m]) {
return x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != '#'; // 假设'#'为障碍物
}
// 广度优先搜索函数
int BFS(int sx, int sy, int ex, int ey, int n, int m, char grid[n][m]) {
vector<vector<bool>> visited(n, vector<bool>(m, false)); // 记录节点是否已访问
queue<Node> q;
Node start = {sx, sy, 0}; // 起点
q.push(start);
visited[sx][sy] = true;
while (!q.empty()) {
Node curr = q.front();
q.pop();
if (curr.x == ex && curr.y == ey) { // 到达终点
return curr.step;
}
// 尝试向四个方向移动
for (int i = 0; i < 4; ++i) {
int nx = curr.x + dx[i];
int ny = curr.y + dy[i];
if (isValid(nx, ny, n, m, grid) && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny, curr.step + 1});
}
}
}
return -1; // 无法到达终点
}
int main() {
int n, m;
cin >> n >> m;
char grid[n][m];
//输入gird
int sx, sy, ex, ey;
// 假设输入起点和终点
cin >> sx >> sy >> ex >> ey;
int result = BFS(sx, sy, ex, ey, n, m, grid);
cout << result << endl;
return 0;
}
谢谢
核心代码
void dfs(int x, int y, int x1, int y1) {
if (sum > minn) {
return;
}
if (x == x1 && y == y1) {
minn = min(sum, minn);
return;
}
else {
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (vis[xx][yy] == 0 && xx >= 1 && yy >= 1 && xx <= n && yy <= m && a[xx][yy] == '*') {
vis[xx][yy] = 1;
sum++;
dfs(xx, yy, x1, y1);
vis[xx][yy] = 0;
sum--;
}
}
}
}
DFS 本身并不保证找到的是最短路径。
需要修改
这题我AC了