走迷宫（bfs，最短路）

Input

10 10

#S######.#

......#..#

.#.##.##.#

.#........

##.##.####

....#....#

.#######.#

....#.....

.####.###.

....#...G#

Output

代码：

#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

typedef pair<int, int> P;

queue<P> pos;

const int maxn = 100;

char maze[maxn][maxn];

using namespace std;

int N, M;   //N, M分别代表行数和列数

int bx = -1, by = -1, ex = -1, ey = -1;     //代表起点和终点

int d[maxn][maxn];  //储存各个点到起点的距离

int dx[] = {1, 0, -1, 0};

int dy[] = {0, 1, 0, -1};   //遍历四个方向

int vis[maxn][maxn];

const int INF = 0x3f3f3f3f;

int bfs()

{

    pos.push(P(bx, by));

    memset(vis, 0, sizeof(vis));

    while(pos.size())

    {

        P p = pos.front();

        pos.pop();

        if(p.first == ex && p.second == ey)

            break;

        vis[p.first][p.second] = 1;

        //遍历四个方向

        for(int i = 0; i < 4; i++)

        {

                int curx = p.first + dx[i], cury = p.second + dy[i];

                if(curx >= 0 && curx < N && cury >= 0 && cury < M && !vis[curx][cury] && maze[curx][cury] != '#')   //说明它还未放入过栈中

                {

                    vis[curx][cury] = 1;        //表示已经访问过

                    pos.push(P(curx, cury));

                    d[curx][cury] = d[p.first][p.second] + 1;

                }

        }

    }

    return d[ex][ey];

}

int main()

{

    cin >> N >> M;

    for(int i = 0; i < N; i++)

        cin >> maze[i];

    for(int i = 0; i < N; i++)

    {

        for(int j = 0; j < M; j++)

        {

            if(maze[i][j] == 'S')

            {

                bx = i;

                by = j;

                d[i][j] = 0;

            }

            else

                d[i][j] = INF;

            if(maze[i][j] == 'G')

            {

                ex = i;

                ey = j;

            }

        }

    }

    int ans = bfs();

    if(ans != INF)

        cout << ans << endl;

    else

        cout << "NO way!" << endl;

}

巴特西

走迷宫（bfs，最短路）

Input

Output

最新文章

热门文章

巴特西

走迷宫（bfs， 最短路）

Input

Output

最新文章

热门文章

走迷宫（bfs，最短路）