迷宫问题 （C++代码）BFS走过路过，不要错过

解题思路:

首先，我的代码有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;

}