题目
题目大意：
这个题目就是大小不超过9*9的迷宫，给你起点终点和起点的方向，让你进行移动
移动特别之处是不一定上下左右都可以，只有根据方向确定可以走的方向。
思路：
需要写一个读入函数，这个需要读入起点，终点，方向（简单），还有就是接下来几行的不同位置
可以转的方向，可以写几个函数，根据函数来判断方向，最后转换成数字，用bool类型数组0，1分别代表
可以或不可以。
之后要写一个bfs，这个比较简单，就是和普通差不多，但是之后要输出路线，所以
要有两个数组，一个用来存储路程，一个用来存储路线。
具体一点的bfs，就是先把初始位置放进去，写清楚距离，之后进去while，while里面要有一个判断
是否到了终点，之后就用walk函数进行走路，然后判断这一步是否合法，合法就走下一步，不过，走下一步之前，记住两个点
第一个就是去记录距离，第二个就是记录路线。
最后有一个输出函数，用vector
这个题目就是大小不超过9*9的迷宫，给你起点终点和起点的方向，让你进行移动
移动特别之处是不一定上下左右都可以，只有根据方向确定可以走的方向。
思路：
需要写一个读入函数，这个需要读入起点，终点，方向（简单），还有就是接下来几行的不同位置
可以转的方向，可以写几个函数，根据函数来判断方向，最后转换成数字，用bool类型数组0，1分别代表
可以或不可以。
之后要写一个bfs，这个比较简单，就是和普通差不多，但是之后要输出路线，所以
要有两个数组，一个用来存储路程，一个用来存储路线。
具体一点的bfs，就是先把初始位置放进去，写清楚距离，之后进去while，while里面要有一个判断
是否到了终点，之后就用walk函数进行走路，然后判断这一步是否合法，合法就走下一步，不过，走下一步之前，记住两个点
第一个就是去记录距离，第二个就是记录路线。
最后有一个输出函数，用vector
总的来说，这也是一个最短路问题，和robot有点像，就是每个位置不一定每个方向都是对的。
复制代码
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138#include <stdio.h> #include <stdlib.h> #include <string.h> #include <queue> #include <algorithm> #include <vector> #include <iostream> using namespace std; string name; int x1,x2,y1,y2,dir,x,y; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; const char *dirs="ESWN"; const char *turns="FLR"; const int maxn=100; bool has_edge[maxn][maxn][10][10]; int d[maxn][maxn][4]; int dir_id(char c) { return (strchr(dirs,c)-dirs); } int turn_id(char c) { return (strchr(turns,c)-turns); } struct node { int x,y,dir; node(int x=0,int y=0,int dir=0):x(x),y(y),dir(dir){} }b[maxn][maxn][4]; node walk(const node& u,int turn) { int dir=u.dir; if(turn==1) dir=(dir+3)%4; if(turn==2) dir=(dir+1)%4; return node(u.x+dx[dir],u.y+dy[dir],dir); } bool scan() { memset(has_edge,0,sizeof(has_edge)); cin>>name; if(name=="END") return false; char s[100]; cin>>x>>y>>s>>x2>>y2; dir=dir_id(s[0]); x1=x+dx[dir]; y1=y+dy[dir]; int r,c; while(cin>>r) { if(r==0) break; cin>>c; char s1[100]; while(cin>>s1) { if(s1[0]=='*') break; int l=strlen(s1); for(int i=1;i<l;i++) { has_edge[r][c][dir_id(s1[0])][turn_id(s1[i])]=1; // printf("has_edge[%d][%d][%d][%d]=1;n",r,c,dir_id(s1[0]),turn_id(s1[i])); } } } cout<<name<<endl; return true; } bool judge(int r, int c) { return r >=1 && r <= 9 && c >= 1 && c <= 9;//迷宫从1开始 } void print_ans(node exa) { vector<node>nodes; while(true) { nodes.push_back(exa); if(d[exa.x][exa.y][exa.dir]==0) break; exa=b[exa.x][exa.y][exa.dir]; } nodes.push_back(node(x,y,dir)); int cnt=0; for(int i=nodes.size()-1;i>=0;i--) { if(cnt%10==0) printf(" "); cnt++; printf(" (%d,%d)",nodes[i].x,nodes[i].y); if(cnt%10==0) printf("n"); } if(cnt%10!=0) printf("n"); } void bfs() { queue<node>que; node exa=node(x1,y1,dir); memset(d,-1,sizeof(d)); d[exa.x][exa.y][exa.dir]=0; que.push(exa); while(!que.empty()) { node exa=que.front(); //printf("%d %d %dn",exa.x,exa.y,exa.dir); que.pop(); if(exa.x==x2&&exa.y==y2) { print_ans(exa); return ; } for(int i=0;i<3;i++) { node v=walk(exa,i); // printf("www %d %d %d %dn",v.x,v.y,v.dir,i); // printf("d[%d][%d][%d]=%dn",v.x,v.y,v.dir,d[v.x][v.y][v.dir]); if(has_edge[exa.x][exa.y][exa.dir][i]&&judge(v.x,v.y)&&d[v.x][v.y][v.dir]<0) { d[v.x][v.y][v.dir]=d[exa.x][exa.y][exa.dir]+1; b[v.x][v.y][v.dir]=exa; //printf("%d %d %dn",v.x,v.y,v.dir); que.push(v); } } } printf(" No Solution Possiblen"); } int main() { while(scan()) { bfs(); } return 0; }
转载于:https://www.cnblogs.com/EchoZQN/p/10356870.html
最后
以上就是满意大地最近收集整理的关于J - Abbott's Revenge 搜索 寒假训练的全部内容，更多相关J内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复