给定一个m*n大小的矩阵T,对于其中的每个位置(i,j),有T[i,j] >=—1:如果T[i,j] =—1则表示该位置为墙;如果T[i,j] >=0为则表示该位置为空,但该位置的权值为T[i,j]。 坐标(1,1)为起点S,坐标(m,n)的位置为终点T(默认这两个位置的元素为0)。请设计一个程序,若该迷宫存在一条路径连接S和T(即该路径所经过的位置的权值皆>=0):则返回连接S和T的一条“最短”路径;否则返回“无”。注意一条连接S和T的路径的“长度”定义为它所走过的位置的权值之和。连接S和T的“最短”路径是指在所有连接S和T的路径当中,长度最小的那一条。 注意在走该迷宫时,每次只能选择“上下左右”四个方向中的一个进行移动。如果将要移动的位置有墙,则待在原地,用c语言编程
时间: 2024-03-09 08:45:40 浏览: 13
以下是使用BFS算法求解迷宫最短路径的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_M 100
#define MAX_N 100
typedef struct {
int x, y; // 表示坐标
int step; // 表示走到该位置的步数
} Node;
int m, n; // 迷宫的行数和列数
int T[MAX_M][MAX_N]; // 存储迷宫信息
int vis[MAX_M][MAX_N]; // 标记某个位置是否已经访问过
int dx[] = {-1, 0, 1, 0}; // 表示四个方向的x方向的增量
int dy[] = {0, 1, 0, -1}; // 表示四个方向的y方向的增量
// 判断一个位置是否可以走
int can_go(int x, int y) {
if (x < 0 || x >= m || y < 0 || y >= n || T[x][y] < 0) {
return 0; // 该位置超出迷宫范围或为墙
}
return 1;
}
// BFS算法求解最短路径
int bfs(int sx, int sy, int tx, int ty) {
Node queue[MAX_M * MAX_N]; // 定义队列
int front = 0, rear = 0; // 定义队列的头和尾
queue[rear++] = (Node){sx, sy, 0}; // 将起点加入队列
vis[sx][sy] = 1; // 标记起点已经访问过
while (front < rear) {
Node cur = queue[front++]; // 取出队列的头
if (cur.x == tx && cur.y == ty) {
return cur.step; // 已经找到终点,返回最短路径长度
}
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (can_go(nx, ny) && !vis[nx][ny]) {
queue[rear++] = (Node){nx, ny, cur.step + T[nx][ny]}; // 加入队列
vis[nx][ny] = 1; // 标记该位置已经访问过
}
}
}
return -1; // 无法从起点走到终点
}
int main() {
scanf("%d %d", &m, &n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &T[i][j]);
}
}
int ans = bfs(0, 0, m - 1, n - 1);
if (ans == -1) {
printf("无\n");
} else {
printf("%d\n", ans);
}
return 0;
}
```
该程序先读入迷宫的大小和信息,然后使用BFS算法求解最短路径,并输出结果。其中,can_go函数用于判断一个位置是否可以走,bfs函数用于实现BFS算法,main函数用于程序的输入和输出。