专栏首页用户6093955的专栏走迷宫(bfs, 最短路)

走迷宫(bfs, 最短路)

Input

10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

Output

22


代码:

#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;



}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 蓝桥杯突击复习准备——部分算法汇总

    当然,上面这个状态转移方程不适用于a数组长度较大的情况。比如AcWing896. 最长上升子序列 II (AC代码,思路在代码中)

    _DIY
  • 【Pet HDU - 4707 】【利用并查集找深度】

    _DIY
  • Dungeon Master POJ - 2251(bfs)

    _DIY
  • 非递归版归并排序

    非递归版的归并排序,省略了中间的栈空间,直接申请一段O(n)的地址空间即可,因此空间复杂度为O(n),时间复杂度为O(nlogn); 算法思想:   开始以间隔...

    用户1154259
  • 1316 文化之旅 2012年NOIP全国联赛普及组

    1316 文化之旅 2012年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 ...

    attack
  • Oil Deposts(dfs)

    题意就是有一大片地方,让你去找里面有多少片油田(八个方向),我们只需要遍历地图,当找到'@'的时候进行dfs,把搜索到的'@'都变成'*'就好了,然后用一个变量...

    Ch_Zaqdt
  • 迷宫的最短路径

    题意:给定一个大小为N * M的迷宫,迷宫由通道与墙壁组成,每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需要的最下步数。

    杨鹏伟
  • GoLang 基础语法

    var a int8 = 10 var b int32 = 10 //编译报错 c := a+b

    luxixing
  • Super Pow:如何高效进行模幂运算

    今天来聊一道与数学运算有关的算法题目,LeetCode 372 题 Super Pow,让你进行巨大的幂运算,然后求余数。

    帅地
  • 675. Cut Off Trees for Golf Event

    You are asked to cut off all the trees in this forest in the order of tree’s he...

    用户1147447

扫码关注云+社区

领取腾讯云代金券