UVA 816 - Abbott's Revenge(BFS)
39 UVa BFS
2023-09-14 09:10:07 时间
UVA 816 - Abbott's Revenge
题意:一个迷宫,每一个点限制了从哪一方向来的。仅仅能往左右前走,然后问起点到终点的最短路径
思路:BFS。每一个点拆成4个方向的点。相应能走的方向建图跑一下bfs就可以
代码:
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <algorithm> using namespace std; const int N = 10005; const int D[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1}; char name[25]; int n, m; vector<int> g[15][15][4]; struct State { int x, y, dir; int pre; } Q[N], s, e; char str[25]; int x, y, vis[15][15][4]; int hash(char c) { if (c == 'F') return 0; if (c == 'R') return 1; if (c == 'L') return -1; if (c == 'N') return 0; if (c == 'E') return 1; if (c == 'S') return 2; return 3; } #define MP(a,b) make_pair(a,b) typedef pair<int, int> pii; vector<pii> ans; void print(int u) { if (u == -1) return; print(Q[u].pre); ans.push_back(MP(Q[u].x, Q[u].y)); } void bfs() { ans.clear(); memset(vis, 0, sizeof(vis)); int head = 0, rear = 0; s.pre = -1; Q[rear++] = s; vis[s.x][s.y][s.dir] = 1; while (head < rear) { State u = Q[head++]; if (u.x == e.x && u.y == e.y) { print(head - 1); int tot = ans.size(); for (int i = 0; i < tot; i++) { if (i % 10 == 0) printf("\n "); printf(" (%d,%d)", ans[i].first, ans[i].second); } printf("\n"); return; } for (int i = 0; i < g[u.x][u.y][u.dir].size(); i ++) { int di = (g[u.x][u.y][u.dir][i] + u.dir + 4) % 4; State v = u; v.x += D[di][0]; v.y += D[di][1]; if (v.x < 0 || v.y < 0) continue; v.dir = di; if (vis[v.x][v.y][v.dir]) continue; vis[v.x][v.y][v.dir] = 1; v.pre = head - 1; Q[rear++] = v; } } printf("\n No Solution Possible\n"); } int main() { while (~scanf("%s", name) && strcmp(name, "END")) { memset(g, 0, sizeof(g)); printf("%s", name); scanf("%d%d%s", &s.x, &s.y, str); s.dir = hash(str[0]); scanf("%d%d", &e.x, &e.y); g[s.x][s.y][hash(str[0])].push_back(0); int x, y; while (scanf("%d", &x) && x) { scanf("%d", &y); while (scanf("%s", str) && str[0] != '*') { int len = strlen(str); for (int i = 1; i < len; i++) g[x][y][hash(str[0])].push_back(hash(str[i])); } } bfs(); } return 0; }
相关文章
- Invalid code signing entitlements. Your application bundle's signature contains
- 【Maven错误】 Non-resolvable parent POM for ...... Return code is: 500 , ReasonPhrase:Internal Server Error. and 'parent.relativePath' points at no local POM @ line 14, column 11
- WampServer64提示You don't have permission to access
- Content type 'application/x-www-form-urlencoded;charset=UTF-8' not supported
- 'JAVAC' 不是内部或外部命令解决方法,记得要重启cmd
- MySQL ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: NO)的真正原因
- UVA 10881 Piotr's Ants(等效变换 sort结构体排序)
- win10 'make' 不是内部或外部命令
- error CS0117: `UnityEditor.EditorUtility' does not contain a definition for `GetAssetPreview'
- Mysql模糊查询 select count(*) from sys_invitation where from_id like '%1006%';
- [Ramda] Count Words in a String with Ramda's countBy and invert
- [AngularJS]14. Live preview 'Review', ng-model
- sql 中 '' 与 null 的区别
- 源码安装mysql5.6x启动报错:[ERROR] Can't find messagefile '/data/mysqldata/3306/english/errmsg.sys'
- Attempt to write to field 'android.support.v4.app.FragmentManagerImpl android.support.v4.app.Fragment.mFragmentManager' on a null object reference
- [TypesScript V4] ${X | Y} - ${W | Z}
- [Javascript] let doesn't hoist -- false
- [FAQ][Hardhat] Error HH501: Couldn't download compiler version 0.8.0. Please check your connection.
- [Flutter] lib/main.dart:1: Warning: Interpreting this as package URI, 'package:flutter_app/main.dart'.
- Atitit.html css 浏览器原理理论概论导论attilax总结
- Atiti. Php Laravel 5.1 环境搭建以及 error 排除
- atitit. web组件化原理与设计
- Atitit.数据库分区的设计 attilax 总结
- atitit.js javascript 调用c# java php后台语言api html5交互的原理与总结p97
- 【例题5-3 UVA - 10815】Andy's First Dictionary
- Bean named 'XXX' is expected to be of type [com.***.XXX] but was actually of type [com.sun.proxy.$Proxy*]
- python setup.py install 报错:error: [WinError 3] 系统找不到指定的路径。: 'C:Program Files (x86)Microsoft Visual Studio 14.0VCPlatformSDKlib
- 解决前面有一篇文章中'flashplayer.so为什么要设置777权限的'问题 的 思考了
- cannot bind non-const lvalue reference of type 'std::__cxx11::string&
- @PathVariable不起作用,报错:Cannot resolve @PathVariable ' '
- [django1.6]跑批任务错误(2006, 'MySQL server has gone away')