1. Johngo学长首页
  2. 技术点详细复盘专题
  3. Linux

POJ1573(Robot Motion)–简单模拟+简单dfs

• Linux • 阅读 103

题目在这里

题意

POJ1573(Robot Motion)--简单模拟+简单dfs

问你按照图中所给的提示走，多少步能走出来？？？

其实只要根据这个提示走下去就行了。模拟每一步就OK，因为下一步的操作和上一步一样，所以简单dfs。如果出现loop状态，只要记忆每个所到的点的第一次的步数，最后总步数减掉它即可

POJ1573(Robot Motion)--简单模拟+简单dfs
2 > File Name: poj1573.cpp
 3 > Author: YeGuoSheng
 4 > Description:
 5 给一个开始位置和一个标记了每个走向的迷宫，问能不能按照每一步的
 6 提示走出迷宫
 7 > Created Time: 2019年07月23日 星期二 17时27分34秒
 8 **********/
9
10 #include
11 #include
12 #include
13 #include
14 #include
15 #include
16 #include 17 #include<set>
18 #include 19 #include
20 #include<string>
21 #include
22 #include
23 using namespace std;
 24 const int maxn = 20;
 25 char g[maxn][maxn];
 26 int vis[maxn][maxn];
 27 int gCount[maxn][maxn];//标记所访问到的点是第几步访问到的
28 int row,col,start;
 29 int Count = 0;
 30 int t = 0;
 31 bool flag = false;//标记是否走出来或死虚幻
32 int p;//记录上一次到达某位置的步数，防止被第二次到达的步数所覆盖
33
34 void dfs2(int x,int y,int Count)
 35 {
 36 if(x==1 && y == start)//回到起始位置结束dfs
37 {
 38 return ;
 39 }
 40 }
 41
42 void dfs(int x,int y,int Count)
 43 {
 44 t = Count;//记录到总步数
45 p = gCount[x][y];//提前保存第一次某点到达的步数
46 gCount[x][y] = t;//更新到当前访问到点的总步数
47 if(x==0 ||y==0 || x == row+1 || y == col+1)//走出去的情况
48 {
 49 flag = true;
 50 return;
 51 }
 52 if(vis[x][y] == 0)//如果当前结点未访问
53 {
 54 vis[x][y] = 1;//标记为1,，然后进行下面的dfs
55 }
 56 else // 1当前位置已经访问过，即接下来将构成死循环
57 {
 58 flag = false;
 59 return ;
 60 }
 61 if(g[x][y] == 'W')//dfs下一个位置
62 {
 63 dfs(x,y-1,Count+1);
 64 return ;
 65 }
 66 else if(g[x][y]=='E')
 67 {
 68 dfs(x,y+1,Count+1);
 69 return ;
 70 }
 71 else if (g[x][y] =='S')
 72 {
 73 dfs(x+1,y,Count+1);
 74 return;
 75 }
 76 else//N
77 {
 78 dfs(x-1,y,Count+1);
 79 return ;
 80 }
 81 }
 82
83 int main()
 84 {
 85 while(scanf("%d%d%d",&row,&col,&start) && row != 0 && col != 0 && start != 0)
 86 {
 87 Count=0;
 88 p = 0;
 89 t = 0;
 90 memset(g,'.',sizeof(g));//边界用‘.’填充
91 memset(vis,0,sizeof(vis));
 92 for(int i =1 ;i <=>//整个Grid加了边界
93 {
 94 for(int j = 1;j <=>)
95 {
 96 cin>>g[i][j];
 97 }
 98 }
 99 dfs(1,start,0);
100 if(flag)
101 {
102 // for(int i = 1;i <=>103 // {
104 // for(int j= 1;j <=>105 // {
106 // cout<<gcount[i][j]<<“>107 // }
108 // cout<109 // }
110 cout<<t<<"</t<<;> step(s) to exit"<<endl;
111 }
112 else
113 {
114 cout<<p<<"</p<<</gcount[i][j]<<“> step(s) before a loop of "<<t-p<<"</t-p<< step(s)"<<endl;
115 }
116 }
117 return 0;
118 }

View Code

Original: https://www.cnblogs.com/ygsworld/p/11233705.html
Author: 回忆酿的甜
Title: POJ1573(Robot Motion)–简单模拟+简单dfs

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/582158/

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
0

【自取】最近整理的，有需要可以领取学习：



Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言 刷题答案下载！

大家都在看

  • Linux 基于flock命令实现多进程并发读写文件控制

    需求描述 实际项目中，需要在Linux下通过 shell脚本并发读写同一个文件，但是希望同一时刻，只有一个进程可以在读、写目标文件。 解决方案 使用 flock命令。 flock …

    Linux 2023年5月27日
    0108

  • 2021年3月-第03阶段-前端基础-JavaScript基础语法-JavaScript基础第01天

    1 – 编程语言 1.1 编程 编程： &#x5C31;&#x662F;&#x8BA9;&#x8BA1;&#x7B97;&amp…

    Linux 2023年6月8日
    0101

  • ASP已老，尚能饭否？

    我对ASP的感情，跟大海一样深。我用它实现了第一个动态网页，也用它做了毕业设计，毕业设计的名字是《毕业设计管理系统》（是不是有点绕）。在 PHP 和 ASP.NET、Java 高歌…

    Linux 2023年6月6日
    0113

  • 搭建Nginx正向代理服务

    需求背景： 前段时间公司因为业务需求需要部署一个正向代理，需要内网服务通过正向代理访问到外网移动端厂商域名通道等效果，之前一直用nginx做四层或者七层的反向代理，正向代理还是第一…

    Linux 2023年6月8日
    0109

  • nacos集群部署

    使用外置数据源-mysql 如果是使用外部数据源，只能是mysql数据库。这样的话需要在mysql数据库里面创建一个数据库，初始化语句在conf目录下，再分配一个可以读写该库的账号…

    Linux 2023年6月8日
    0105

  • Linux 0.11源码阅读笔记-块设备驱动程序

    块设备驱动程序 块设备驱动程序负责读写块设备数据。内核代码使用缓冲区块与块设备(如磁盘)间接交换数据，缓冲区数据通过块设备驱动程序和块设备交换。 [En] The block de…

    Linux 2023年5月27日
    0109

  • 搭建NFS文件共享系统

    1、概述： NFS(Network File System)意为网络文件系统，它最大的功能就是可以通过网络，让不同的机器不同的操作系统可以共享彼此的文件。简单的讲就是可以挂载远程主…

    Linux 2023年6月7日
    0103

  • Docker安装及配置镜像加速

    Docker 支持 Mac Windows Linux 的三种安装 1、系统要求 官网提示如果要安装 Docker Engine， 需要一个CentOS 7 以及以上的稳定版本。 …

    Linux 2023年5月27日
    0114

  • SpringSecurity 新版2.7以上 快速入门

    SpringSecurity 快速入门 1、导入依赖 org.springframework.boot spring-boot-starter-security 2、测试三种权限 …

    Linux 2023年6月7日
    0113

  • 多级缓存-redis缓存预热

    冷启动：服务刚刚启动时，Redis中并没有缓存，如果所有商品数据都在第一次查询时添加缓存，可能会给数据库带来较大压力。 缓存预热：在实际开发中，我们可以利用大数据统计用户访问的热点…

    Linux 2023年5月28日
    096

  • 如何在 pyqt 中解决启用 DPI 缩放后 QIcon 模糊的问题

    问题描述 如今显示器的分辨率越来越高，如果不启用 DPI 缩放，软件的字体和图标在高分屏下就会显得非常小，看得很累人。从 5.6 版本开始，Qt 便能支持 DPI 缩放功能，Qt6…

    Linux 2023年6月7日
    0208

  • Windows下的SSH Server

    （请注意，本文内容以杂谈为主，稍微提及了一些在MobaXterm中开启SSH Server可能遇到的情况和解决方法，没有多少干货，请酌情查看，谢谢） 最近比较无聊，使用MobaXt…

    Linux 2023年6月6日
    0112

  • 【Example】C++ 标准库 std::atomic 及 std::memory_order

    C++ 标准库提供了原子操作。（我已经懒得写序言了） ==================================== 先来说原子操作的概念： 原子操作是多线程当中对资源进…

    Linux 2023年6月13日
    080

  • CentOS shell中的变量

    shell中的变量 变量的介绍 变量即变化的量，核心是”变”与”量”二字，变即变化，量即衡量状态。 量：是记录现实世界当中的某种状态…

    Linux 2023年6月7日
    099

  • 【Hash篇】哈希计算神器-HashMyFiles

    可直接拖放、复制粘贴、添加文件或文件夹的方式来批量计算Hash，操作简便、体积小、免费。这篇来介绍他的汉化和其它一些功能设置—【suy】 目录 1、绿色便携 2、批量算…

    Linux 2023年6月13日
    0107

  • redis批量删除key 远程批量删除key

    一、遇到的问题 在开发的过程中，经常会遇到要批量删除某种规则的key，如缓存的课程数据”course-课程uid”，其中课程uid是变量，我们需要删除&#8…

    Linux 2023年5月28日
    088
亲爱的 Coder【最近整理，可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球