迷宫的最短路径 -- BFS

简介:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
using namespace std;

#define MM(a) memset(a,0,sizeof(a))

typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 2*1e3+5;
const int INF = 1e9+5;
const int mod = 1000000007;
const double eps = 1e-7;

char map[105][105];
int dis[105][105];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int n, m;
int sx, sy, ex, ey;

typedef pair <int, int> P;
void Init()
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            dis[i][j] = INF;
        }
    }
}
int BFS()
{
    queue<P> que;
    Init();
    que.push(P(sx,sy));
    dis[sx][sy] = 0;
    while(que.size())
    {
        P p = que.front();
        que.pop();
        if(p.first==ex && p.second==ey)
            break;
        for(int i=0; i<4; i++)
        {
            int nx = p.first+dx[i];
            int ny = p.second+dy[i];
            if(nx>=0 && nx<n && ny>0 && ny<m && map[nx][ny]!='#' &&
               dis[nx][ny]==INF)
            {
                que.push(P(nx, ny));
                dis[nx][ny] = dis[p.first][p.second]+1;
            }
        }
    }
    return dis[ex][ey];
}
int main()
{
    while(cin>>n>>m)
    {
        for(int i=0; i<n; i++)
            cin>>map[i];
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(map[i][j] == 'S')
                {
                    sx = i;
                    sy = j;
                }
                if(map[i][j] == 'E')
                {
                    ex = i;
                    ey = j;
                }
            }
        }
        printf("%d\n",BFS());
    }
    return 0;
}
/**
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...E#
**/

目录
相关文章
|
11月前
|
Prometheus 运维 监控
别再裸奔搞监控了!一篇带你上手 Prometheus+Grafana 的实战指南
别再裸奔搞监控了!一篇带你上手 Prometheus+Grafana 的实战指南
1598 2
|
SQL 数据可视化 数据挖掘
让项目数据更有说服力:五款必备数据可视化管理工具推荐
在现代企业管理中,数据是决策的重要依据。有效的数据可视化工具能帮助项目经理快速洞察项目进展、评估风险、优化资源配置。本文推荐五款必备的数据可视化管理工具,包括板栗看板、Power BI、Tableau、Google Data Studio和Qlik Sense,从功能、易用性和优缺点等方面进行全面评析,帮助您将数据转化为行动,推动项目高效前行。
929 4
|
JSON 数据挖掘 API
深入研究:京东商品评论API详解
京东商品评论API助力电商数据分析与优化。通过该接口,开发者可获取商品评论内容、时间、评分等详细信息,以及好评率、差评率等统计数据。适用于用户体验分析、市场调研等场景。使用前需注册开发者账号、申请权限,并正确配置参数(如app_key、商品ID等)。返回数据为JSON格式,便于解析与应用。
748 10
|
图形学
【unity小技巧】unity最完美的CharacterController 3d角色控制器,实现移动、跳跃、下蹲、奔跑、上下坡、物理碰撞效果,复制粘贴即用
【unity小技巧】unity最完美的CharacterController 3d角色控制器,实现移动、跳跃、下蹲、奔跑、上下坡、物理碰撞效果,复制粘贴即用
5719 0
|
JSON Ubuntu Linux
FreeSWITCH安装
FreeSWITCH
3135 0
FreeSWITCH安装
|
Linux Docker 容器
『Docker』在Docker快速部署.NET Core项目
📣读完这篇文章里你能收获到 - 在Docker快速部署.NET Core项目
1096 0
『Docker』在Docker快速部署.NET Core项目
Mac 解压zip文件错误:无法将"*.zip"解压缩到"" (错误 1-操作不被允许)
错误提示:   无法将"*.zip"解压缩到"" (错误 1-操作不被允许)或者 解压缩失败   英文提示: "Unable to unarchive into file path" (Error 1 - Operation not permitted.) or "Decompression Failed" 结局方法:   用终端unzip 命令进行解压:   打开终端(Terminal),输入unzip 然后拖拽zip文件到unzip后面,回车,进行命令解压。
12552 1
|
SQL 安全 Java
学习MyBatis必知必会(4)~ OGNL 表达式和EL 表达式
学习MyBatis必知必会(4)~ OGNL 表达式和EL 表达式
901 0
|
.NET Windows
ASP.NET速度优化
用过ASP.NET的人都知道吧,页面首次打开很慢,本来网站第一次启动就慢,但别的页面如果没有访问过的第一次访问也会慢。 原因:asp.net程序第一次运行需要验证数字签名,这个验证需要远程连接微软服务器去验证,明显会让用户感觉速度很卡,当服务器是无法连接到外网时,这个校验证书的过程需要等到timeout之后才会结束,有时候会延迟很久。
1125 0