我是靠谱客的博主 闪闪草莓,这篇文章主要介绍Uva 816(bfs求最短路),现在分享给大家,希望可以做个参考。

复制代码
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
#include <bits/stdc++.h> using namespace std; struct Node{ int r,c,dir; Node(int r=0, int c=0, int dir=0):r(r),c(c),dir(dir) {} }; int have_edge[10][10][4][3];//当前状态 最后一维为是否可以沿着转弯的方向行走 int d[10][10][4];//表示初始状态到此状态的最短路长度 Node pre[10][10][4]; int r0,c0,r1,c1,rf,cf,init_dir; const char* dirs = "NESW"; const char* turns = "FLR"; int id_dir(char s){ return strchr(dirs,s) - dirs;}// 0123 int id_turn(char s){return strchr(turns,s) - turns;}//0不动 1左 顺时针 2右 逆时针 const int dr[] = {-1, 0, 1, 0}; //dirs为上右下左 dr[]和dc[]分别接受一个方向来判断row and col的变化 const int dc[] = {0, 1, 0, -1}; bool input(){ char s1[99], s2[99]; if(scanf("%s%d%d%s%d%d",s1,&r0,&c0,s2,&rf,&cf) != 6) { return false;} printf("%sn", s1); init_dir = id_dir(s2[0]); r1 = r0 + dr[init_dir]; c1 = c0 + dc[init_dir]; // printf("%d %d %dn", init_dir,r1,c1); memset(have_edge,0,sizeof(have_edge)); for(;;){ int r,c; scanf("%d", &r); if(r == 0) break; scanf("%d", &c); while(scanf("%s", &s2) && s2[0] != '*'){ int len = strlen(s2); for(int i = 1; i < len; i++){ have_edge[r][c][id_dir(s2[0])][id_turn(s2[i])] = 1; } } } return true; } Node walk(Node u, int turn){ // int dir = u.dir; if(turn == 1) dir = (u.dir+3)%4; else if(turn == 2) dir = (u.dir+1) %4; return Node(u.r + dr[dir], u.c + dc[dir] , dir); } bool inside(int r, int c) { return r >= 1 && r <= 9 && c >= 1 && c <= 9; } void print_ans(Node u){ vector<Node> ans; for(;;){ ans.push_back(u); if(d[u.r][u.c][u.dir] == 0) break; u = pre[u.r][u.c][u.dir]; //根据最后一个节点回溯打印解 } ans.push_back(Node(r0,c0,init_dir)); int cnt = 0; for(int i = ans.size() -1; i >= 0; i--){ if(cnt % 10 == 0) printf(" "); printf(" (%d,%d)", ans[i].r, ans[i].c); if(++cnt % 10 == 0) printf("n"); } if(ans.size() % 10 != 0) printf("n"); } void solve(){ queue<Node> q; memset(d,-1,sizeof(d)); d[r1][c1][init_dir] = 0; Node u(r1,c1,init_dir); q.push(u); while(!q.empty()){ Node u = q.front(); q.pop(); // printf("$ u %d %d %dn",u.r, u.c,u.dir); if(u.r == rf && u.c == cf){ print_ans(u); return; } for(int i = 0; i < 3; i++){ Node v; if(have_edge[u.r][u.c][u.dir][i]) v = walk(u,i); // printf("& v %d %d %dn",v.r, v.c, v.dir); if(inside(v.r,v.c) && d[v.r][v.c][v.dir] < 0){ d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1; pre[v.r][v.c][v.dir] = u; q.push(v); } } } printf(" No Solution Possiblen"); } int main(){ while(input()){ solve(); } return 0; }

最后

以上就是闪闪草莓最近收集整理的关于Uva 816(bfs求最短路)的全部内容,更多相关Uva内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(86)

评论列表共有 0 条评论

立即
投稿
返回
顶部