获取中...

-

Just a minute...

迷宫问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<cstdio>
using namespace std;
int map[10000][10000]; //定义迷宫的大小
int Min=999999; //确保Min>step
int vis[10000][10000]; //用来标记
int dir[4][2]={1,0,0,1,-1,0,0,-1}; //迷宫的四个方向
struct node //定义迷宫的位置
{
int x, y; //x,y为迷宫的当前位置
}a,temp[10000];
stack<node> s; //定义一个栈
int m = 0; //迷宫的初始步数
int p,q; //p,q为迷宫的行和列
void dfs(int x, int y, int step) //x,y为迷宫的当前位置
{
if(x == p-1 && y == q-1) //判断是否到达出口
{
if(step < Min) //判断是否是最小步数
{
m = 0;
Min = step ; //记录最小步数
while(!s.empty()) //判断是否栈空,栈空结束,
{
temp[m++] = s.top(); //temp像当于临时变量,从栈顶到栈底相当于终点到起点的路径
s.pop(); //将数据弹出栈
}
for(int i = m-1; i >= 0; i--) //循环temp[m-1]到temp[0]是起点到终点
{
s.push(temp[i]); //将数据入栈
}
return ;
}
}
for(int i = 0; i < 4; i++) //从四个方向判断是否能走
{
int nx = x + dir[i][0];
int ny = y + dir[i][1]; //nx,ny是迷宫下一个位置的坐标
if(!vis[nx][ny] && map[nx][ny] == 0 && nx >= 0 && nx < p && ny >= 0 && ny < q)
//map[nx][ny]==0判断是否能走,!vis[nx][ny]判断是否标记过,nx >= 0 && nx < p && ny >= 0 && ny < q判断是否出界
{
a.x = nx, a.y = ny;
s.push(a); //将走过的点入栈
vis[nx][ny] = 1; //并标记为1
dfs(nx, ny, step+1); //继续向下探寻
s.pop(); //出栈,回溯
vis[nx][ny] = 0; //标记为没有走过
}
}
}
int main()
{
scanf("%d %d",&p,&q) ; //输入迷宫的行和列
for(int i = 0; i <= p-1; i++) //手动输入迷宫
{
for(int j = 0; j < q; j++)
{
cin >> map[i][j];
}
}
vis[0][0]=1; //标记起点为走过
dfs(0,0,0); //从(0,0)开始,初始步数为0
printf("steps = %d\n", Min); //输出最小步数
printf("(0, 0)\n"); //输出起点
for(int i=Min - 1; i>= 0; i--) //输出最短路径
{
cout << "(" << temp[i].x << ", " << temp[i].y << ")"<< endl;
map[temp[i].x][temp[i].y]=2; //标记最短路径为2
map[0][0]=2; //标记起点为2
}
for(int i = 0; i <= p-1; i++) //输出标记过最短路径的迷宫
{
for(int j = 0; j < q; j++)
{
cout<<map[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
相关文章
评论
分享
  • 十大排序

    冒泡排序,选择排序,插入排序,希尔排序,归并排序,快速排序,堆排序,计数排序,桶排序,基数排序 ** 稳定:** 如果a原本在b前面,而a=b,排序之后a仍然在b的前面;** 不稳定:** 如果a原本在b的前面,而a=b,排序之后a...

    十大排序
  • 网鼎杯部分wp

    pwnboom1分析远程已经打不通了,远程的偏移和本地的偏移不一样,只能复现一下本地的了。 首先看到流程图,代码量很大,有很大的switch语句和嵌套结构,可能是虚拟机或者是解析器。 从下图看出是一个C语言的解析器。 然后看了...

    网鼎杯部分wp
  • 网络设备配置与管理

    Linux网络设备与管理大作业 下图为某企业网络拓扑图,接入层采用二层交换机2960,汇聚和核心层使用了一台三层交换机3560 24PS,局域网边缘采用一台路由器LanRouter用于连接到外部网络的Isp Router两台路由器...

    网络设备配置与管理
Please check the parameter of comment in config.yml of hexo-theme-Annie!