您现在的位置是:首页 > 正文

Yuchang and Zixiang ‘s maze(BFS)

2024-02-29 15:30:51阅读 0

题目链接:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
const int maxn=1010;
char map[maxn][maxn];
int vis[maxn][maxn];
int step[maxn][maxn];
int n,m;
int Move[4][2]={1,0,-1,0,0,1,0,-1};
struct point{
    int x,y;
}in,out,beg;
int check(int x,int y)
{
    if(vis[x][y]==0&&x>=1&&x<=n&&y>=1&&y<=m&&map[x][y]!='#')
        return 1;
    else
        return 0;
}
int bfs()
{
    memset(vis, 0, sizeof(vis));
    memset(step, 0, sizeof(step));
    vis[beg.x][beg.y]=1;
    step[beg.x][beg.y]=0;
    queue<point>q;
    q.push(beg);
    while (!q.empty())
    {
        out=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            in.x=out.x+Move[i][0];
            in.y=out.y+Move[i][1];
            if(check(in.x,in.y))
            {
                if(map[in.x][in.y]=='E')
                {
                    return step[out.x][out.y]+1;
                }
                q.push(in);
                vis[in.x][in.y]=1;
                step[in.x][in.y]=step[out.x][out.y]+1;
            }
        }
    }
    return -1;
}
int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                map[i][j]='.';
            }
        }
        int t;
        scanf("%d",&t);
        while (t--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            map[x][y]='#';
        }
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if(a==c&&b==d)
        {
            printf("0\n");
        }
        else
        {
            map[a][b]='S';
            map[c][d]='E';
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(map[i][j]=='S')
                    {
                        beg.x=i;
                        beg.y=j;
                    }
                }
            }
            int ans=bfs();
            printf("%d\n",ans);
        }
    }
    return 0;
}

 

网站文章

  • 一文读懂物联网、云计算与大数据的关系

    一文读懂物联网、云计算与大数据的关系

    ARM是微处理器行业的一家知名企业,设计了大量高性能、廉价、耗能低的RISC处理器、相关技术及软件。技术具有性能高、成本低和能耗省的特点。适用于多种领域,比如嵌入控制、消费/教育类多媒体、DSP和移动式应用等。ARM公司是专门从事基于RISC技术芯片设计开发的公司,作为知识产权供应商,本身不直接从事芯片生产,而是转让设计许可,由合作公司生产各具特色的芯片...

    2024-02-29 15:30:24
  • 系统分析师选择题笔记

    系统分析师选择题笔记

    目录分值:4分中国公民、法人或者其他组织的作品,不论是否发表,都享有著作权。开发软件所用的思想、处理过程、操作方法或者数学概念不受保护软件作品并不是指代码,而是指带有特定业务逻辑的程序以及软件文档★著作权法不适用于下列情形:法律、法规,国家机关的决议、决定、命令和其他具有立法、行政、司法性质的文件,及其官方正式译文;时事新闻;历法、通用数表、通用表格和公式。分值:1分

    2024-02-29 15:30:16
  • 反调试与反反调试学习·1(挖坑)

    文章目录个人理解静态反调试PEBTEB原始API攻击调试器打开进程检查TLS回调函数使用普通API动态反调试使用SEH时间检查单步检查补丁检查反反汇编偷取代码分页保护壳虚拟机 个人理解   2019....

    2024-02-29 15:30:07
  • 顺丰面试,第二个问题把我劝退了!

    你好,我是田哥本文主人翁是我星球里一位同学,周一线上顺丰面试遇到的问题,反馈面经时,只记得部分的。本来约的三点的面试,但是面试官提前上线看到我在线就说提前开始吧。先看问题 自我介绍说一个你认为有挑战的...

    2024-02-29 15:30:00
  • 程序员是怎么约会的?

    程序员是怎么约会的?

    程序员? 在多数心目印象当中,程序员大多数是宅男。程序员的世界是由代码构建的,代码之外还是代码。 程序员的世界是:格子衫,牛仔裤,其实,在程序员眼里衣服就是块布,避体不贵,经济实惠。省下的钱用来买个一...

    2024-02-29 15:29:31
  • 分布式设计原则

    分布式设计原则

    1、CAP理论2000年Eric Brewer教授提出了著名的CAP理论,即:一个分布式系统不可能满足一致性,可用性和分区容错性这三个需求,最多只能同时满足两个。2002年MIT的Seth Gilbert 和 Nancy lynch两人证明了CAP理论的正确性。根据CAP理论,一致性(C),可用性(A),分区容错性(P),三者不可兼得,必须有所取舍。因此系统架构师不要把精力浪费在如何设

    2024-02-29 15:29:23
  • Silverlight/Windows8/WPF/WP7/HTML5周学习导读(8月27日-9月2日)

    Silverlight/Windows8/WPF/WP7/HTML5周学习导读(8月27日-9月2日)

    Silverlight/Windows8/WPF/WP7/HTML5周学习导读(8月27日-9月2日)本周Silverlight学习资源更新Silverlight 3D 投射mypc2010Silverlight RIA Service部署到IIS6的步骤或问题边缘程序员2011Silverlight找到模板中的子控件sb001Silverlight中读取Word边缘程序员2011基于Silver

    2024-02-29 15:29:15
  • C++网络编程-高性能服务器编程

    C++网络编程-高性能服务器编程

    一个进程给其他进程发送信号的api是kill函数。

    2024-02-29 15:28:44
  • C++之将一个数的【各个位数】分别输出, 这个数可以是个位数、十位数、百位数、千位数、万位数.....

    C++之将一个数的【各个位数】分别输出, 这个数可以是个位数、十位数、百位数、千位数、万位数.....

    这个题目的要求是,输入一个数,然后将这个数的各个位上的数字输出出来,这个数可以是1位数,2位数,3位数,4位数,5位数,6位数,7位数,8位数...... 如果我们叫这个数为m, 如果m=45678,...

    2024-02-29 15:28:36
  • python:threading.Thread类的使用详解 热门推荐

    Python Thread类表示在单独的控制线程中运行的活动。有两种方法可以指定这种活动: 1、给构造函数传递回调对象mthread=threading.Thread(target=xxxx,args=(xxxx)) mthread.start()2、在子类中重写run() 方法 这里举个小例子:import threading, time class MyThread(threading.Th

    2024-02-29 15:28:09