宝藏地宫只有一个门,即入口。宝藏地宫中有藏有一件宝物。一名 宝藏猎人从入口走进地宫,地宫中设置很多墙壁,对前进方向形成了多处障碍。 宝藏猎人需要在地宫中寻找通路并找到宝藏。 [要求] (1)输入数据:((x1,y1),(x2,y2)),其中 (x1,y1)是地宫入口,(x2,y2)是宝藏位置。地宫中 的墙壁可以任意设置,宝藏位置也可以任意设置。 (2)输出格式:中文提示按照 “找到宝藏,通路为(x1,y1)……….. (x2,y2)”。C语言实现并采用结构体
时间: 2024-03-26 08:38:45 浏览: 138
初中语文 议论文阅读理解分类练习 每人都有一个宝藏 新人教版
好的,以下是采用结构体的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int x;
int y;
} Point;
void search_treasure(int **maze, int rows, int cols, Point start, Point end) {
int **visited = (int **) malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
visited[i] = (int *) malloc(cols * sizeof(int));
for (int j = 0; j < cols; j++) {
visited[i][j] = 0;
}
}
Point *stack = (Point *) malloc(rows * cols * sizeof(Point));
int top = 0;
stack[top] = start;
visited[start.x][start.y] = 1;
while (top >= 0) {
Point p = stack[top--];
if (p.x == end.x && p.y == end.y) {
printf("找到宝藏,通路为(%d,%d)...(%d,%d)\n", stack[0].x, stack[0].y, p.x, p.y);
free(stack);
for (int i = 0; i < rows; i++) {
free(visited[i]);
}
free(visited);
return;
}
if (p.x > 0 && visited[p.x - 1][p.y] == 0 && maze[p.x - 1][p.y] == 0) {
stack[++top] = (Point) {p.x - 1, p.y};
visited[p.x - 1][p.y] = 1;
}
if (p.x < rows - 1 && visited[p.x + 1][p.y] == 0 && maze[p.x + 1][p.y] == 0) {
stack[++top] = (Point) {p.x + 1, p.y};
visited[p.x + 1][p.y] = 1;
}
if (p.y > 0 && visited[p.x][p.y - 1] == 0 && maze[p.x][p.y - 1] == 0) {
stack[++top] = (Point) {p.x, p.y - 1};
visited[p.x][p.y - 1] = 1;
}
if (p.y < cols - 1 && visited[p.x][p.y + 1] == 0 && maze[p.x][p.y + 1] == 0) {
stack[++top] = (Point) {p.x, p.y + 1};
visited[p.x][p.y + 1] = 1;
}
}
printf("无法找到宝藏\n");
free(stack);
for (int i = 0; i < rows; i++) {
free(visited[i]);
}
free(visited);
}
int main() {
int rows, cols;
printf("请输入地宫的行数和列数:");
scanf("%d%d", &rows, &cols);
int **maze = (int **) malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
maze[i] = (int *) malloc(cols * sizeof(int));
for (int j = 0; j < cols; j++) {
maze[i][j] = 0;
}
}
Point start, end;
printf("请输入入口坐标(x1,y1):");
scanf("%d%d", &start.x, &start.y);
printf("请输入宝藏坐标(x2,y2):");
scanf("%d%d", &end.x, &end.y);
printf("请输入地宫的墙壁坐标,以-1,-1表示输入结束:\n");
int x, y;
while (scanf("%d%d", &x, &y) != EOF && x != -1 && y != -1) {
maze[x][y] = 1;
}
search_treasure(maze, rows, cols, start, end);
for (int i = 0; i < rows; i++) {
free(maze[i]);
}
free(maze);
return 0;
}
```
在这个程序中,`Point` 结构体表示一个二维坐标,`maze` 数组表示地宫的二维数组,`search_treasure` 函数使用 DFS 算法来寻找通路,`main` 函数用于读入输入数据并调用 `search_treasure` 函数来解决问题。
阅读全文