解题思路:
首先,我的代码有100多行,不过不要紧思路很简单就是广度优先搜索。
说一下解题思路。
首先,创建一个map【】【】存迷宫地图,给迷宫包层墙。如下图。
图1
其次,在建立一个记录该点到原点的距离的二维数组visited【】【】
图2
BFS:
1.S入队
2.只要队不为空,不断循环。
3.出队一个点temp,判断其上下左右4个点<m,n>,如果不是墙且
visited[temp->y][temp->x] + 1 < visited[m][n],则入队。
参考代码:
include<cstdio>
#include<queue>
#include<malloc.h>
#include<limits.h>
using namespace std;
char map[110][110];
int visited[110][110];
int start_y, start_x;//S的坐标
int end_x,end_y;//E的坐标
typedef struct Node {
int y;
int x;
}*node;//坐标
queue<node> Q;
void initmap(int y, int x) {//初始化地图,如图1
for (int i = 0;i <= x + 1;i++) {
map[0][i] = '#';
map[y + 1][i] = '#';
}//for
int i ,j;
for ( i = 1;i <= y;i++) {
map[i][0] = '#';
for (j = 1;j <= x;j++) {
scanf("%c", &map[i][j]);
if (map[i][j] == ' ' || map[i][j] == '\n') {
j--;
continue;
}//if
}//for
map[i][j] = '#';
}//for
}//initmap
void initvisited(int y, int x) {//初始化每个点到原点的距离,除了S之外,其他的距离都是INT_MAX
for (int i = 0;i < y + 2;i++) {
for (int j = 0;j < x + 2;j++)
visited[i][j] = INT_MAX;
}//for
visited[start_y][start_x] = 0;
}//initvisited
void search(int y, int x) {//找出S,E的坐标
int stop = 0;
for (int i = 0;i < y + 2;i++)
for (int j = 0;j < x + 2&&stop!=2;j++) {
if (map[i][j] == 'S') {
start_x = j;
start_y = i;
stop++;
}//if
if (map[i][j] == 'E') {
end_x = j;
end_y = i;
stop++;
}//if
}//for
}//search
void BFS(int y,int x) {
initmap(y, x);
search(y,x);
initvisited(y, x);
node head = (node)malloc(sizeof(struct Node));
head->x = start_x;
head->y = start_y;
Q.push(head);
while (!Q.empty()) {
node temp = Q.front();
Q.pop();
if(temp!=NULL)
for (int m = temp->y-1;m <= temp->y + 1;m++) {
int n = temp->x;
if (map[m][n] != '#') {
if (visited[temp->y][temp->x] + 1 < visited[m][n]) {
node t1 = (node)malloc(sizeof(struct Node));
t1->x = n;
t1->y = m;
Q.push(t1);
visited[m][n] = visited[temp->y][temp->x] + 1;
}//if
}//if
}//for
for (int n = temp->x-1;n <= temp->x + 1;n++) {
int m = temp->y;
if (map[m][n] != '#') {
if (visited[temp->y][temp->x] + 1 < visited[m][n]) {
node t1 = (node)malloc(sizeof(struct Node));
t1->x = n;
t1->y = m;
Q.push(t1);
visited[m][n] = visited[temp->y][temp->x] + 1;
}//if
}//if
}//for
free(temp);
}//for
if (visited[end_y][end_x] != INT_MAX) {
printf("%d\n",visited[end_y][end_x]);
}else {
printf("-1\n");
}
}
int main() {
int S,size_x,size_y;
scanf("%d", &S);
for (int i = 0;i < S;i++) {
scanf("%d%d",&size_y,&size_x);
BFS(size_y, size_x);
}//for
return 0;
}
0.0分
1 人评分
C二级辅导-进制转换 (C语言代码)浏览:514 |
小九九 (C语言代码)浏览:817 |
C语言训练-字符串正反连接 (C语言代码)浏览:622 |
时间转换 (Java代码)浏览:574 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:1515 |
P1001 (C语言代码)浏览:800 |
C语言程序设计教程(第三版)课后习题1.5 (C++代码)浏览:1080 |
Cylinder (C语言描述+详细分析)浏览:3264 |
矩阵乘方 (C语言代码)浏览:1023 |
演讲大赛评分 (C语言代码)浏览:1630 |