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

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

• Linux • 阅读 89

题目在这里

题意

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语言 刷题答案下载！

大家都在看

  • 用全域安全防范美国NSA对西工大的网络攻击

    上周写的一篇文章《全域安全：一种运行时安全管理模型》，向大家介绍了全域安全管理模型，它是如何在Laxcus分布式操作系统的分布环境下，解决了分布式应用业务的全流程安全管理问题。其中…

    Linux 2023年6月6日
    0100

  • Redis 事务与锁

    基本操作 事务的基本操作 开启事务，设定事务的开启位置，此指令执行后，后续的所有指令均加入到事务中 multi 取消事务，终止当前事务的定义，发生在 multi 之后，exec 之…

    Linux 2023年5月28日
    076

  • CSS中content属性的妙用

    前言 本文讲解CSS中使用频率并不高的content属性，通过多个实用的案例，带你由浅入深的掌握content的用法，让代码变得更加简洁、高效。 定义 W3school中这样定义：…

    Linux 2023年6月7日
    0128

  • Redis的发布订阅及.NET客户端实现

    序言 发布订阅在设计模式中也可以说是观察者模式，针对这个模式是处理对象间一对多的依赖关系的，当一个对象发生变化，其它依赖他的对象都要得到通知并更新。 然而它也有自己的缺点，就是当主…

    Linux 2023年5月28日
    0112

  • redis查看状态信息

    redis查看状态信息 info all|default Info 指定项 server服务器信息 redis_version : Redis 服务器版本 redis_git_sh…

    Linux 2023年5月28日
    094

  • [Git系列] Git 基本概念

    版本控制系统 版本控制系统是一种帮助软件开发者实现团队合作和历史版本维护的软件，一个版本控制系统应具备以下列出的这几个基本功能： 允许开发者并发工作； 不允许一个开发者覆写另一个开…

    Linux 2023年6月14日
    097

  • Python递归遍历目录下所有文件

    递归遍历目录下所有文件 方法一 import os def gci(filepath): #遍历filepath下所有文件，包括子目录 files = os.listdir(fil…

    Linux 2023年6月13日
    0108

  • Linux 查看运行中进程的 umask

    线上某台虚机因为故障重装了系统（基线 CentOS 6.9 内核 2.6.x），重新部署了应用。这个应用会生成一个文件，到NFS挂载目录。 而这个 NFS 挂载目录是一个 FTP …

    Linux 2023年5月27日
    0148

  • Linux 配置Git

    前言：请各大网友尊重本人原创知识分享，谨记本人博客： 南国以南i 一、用git –version命令检查是否已经安装 二、下载git源码并解压 wget https:/…

    Linux 2023年5月27日
    0126

  • 附032.Kubernetes实现蓝绿发布

    蓝绿发布原理 蓝绿发布本质上是希望能优雅无误的迭代应用，以便于使应用平稳提供服务。通常是不停老版本的同时对新版本进行先发布，然后确认无误后进行流量切换，即并行部署。Kubernet…

    Linux 2023年6月13日
    087

  • [云计算]OpenStack这一篇就够了！

    OpenStack简介 OpenStack背景介绍 OpenStack应用场景 OpenStack发展历程 OpenStack架构 架构设计原则 架构全景图 核心服务组件 系统通信…

    Linux 2023年6月13日
    0229

  • 数据结构-树

    404. 抱歉，您访问的资源不存在。 可能是网址有误，或者对应的内容被删除，或者处于私有状态。 代码改变世界，联系邮箱 contact@cnblogs.com 园子的商业化努力-困…

    Linux 2023年6月11日
    0107

  • Apache Bench压力测试使用方法

    Apache Bench是Apache轻量级压力测试工具，使用方便，简单，本文章简单介绍Windows平台使用Apache bench进行接口压力测试（ab测试） ApacheBe…

    Linux 2023年6月8日
    092

  • Powershell 测量命令执形时间

    powershell -Command (Measure-Command { "docker build –no-cache -f 2.2/Dockerfile 2.2…

    Linux 2023年5月28日
    072

  • 四年测试的面试题分享

    其实想说为什么每次面试都要先来点自我介绍，说来说去简历上都有，我曾想过不能快速进入面试阶段嘛 我的专业技能： 基本上这些专业技能是在工作上用过或者自己摸索过，实战经验比较少，下面是…

    Linux 2023年6月8日
    080

  • Linux ARM中断后的处理(5)【转】

    1. 中断进入自定义函数 在中断发生后，经历ARM通用的处理阶段,到达irq_handler宏，转入C语言阶段。 //arch/arm/kernel/entry-armv.S/**…

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