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

题目在这里

题意

：

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

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

  1 /*************************************************************************
  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 <= row;i++)//整个Grid加了边界
 93         {
 94             for(int j = 1;j <= col;j++)
 95             {
 96                 cin>>g[i][j];
 97             }
 98         } 
 99         dfs(1,start,0);
100         if(flag)
101         {
102             // for(int i = 1;i <= row;i++)
103             // {
104             //     for(int j= 1;j <= col;j++)
105             //     {
106             //         cout<107             //     }
108             //     cout<109             // }
110             cout<" step(s) to exit"<<endl;
111         }
112         else
113         {
114             cout<" step(s) before a loop of "<" step(s)"<<endl;
115         }
116     }
117     return 0;
118 }
模拟pojdfs

相关

docker-compose fastdfs

使用webgl(three.js)搭建一个3D智慧园区、3D建筑，3D消防模拟，web版3D,bim管理系统——第

noip多校模拟30

2019.11.8模拟赛

hdfs的写入过程和读取过程

[NOIP模拟赛] 2021.11.16

20211116 NOIP 模拟赛

项目实战：Qt+C#轨道交通行业高性能高流畅度模拟火车移动图像控件

ASP.NET Core管道深度剖析（2）：创建一个“迷你版”的管道来模拟真实管道请求处理流程

NOIP模拟99(多校31)

20210628模拟赛解题报告

20201115gryz模拟赛解题报告

标签