题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1728
思路 BFS 一开始 从开始位置 往四周走 如果能走的话 这个时候 转弯次数都是0
我们的标记不是简单的标记
我们给每个已经访问过的位置 第一次访问时 我们将此时的转弯次数 赋值给它
当下一次 有其他状态 又来访问的时候，我们判断一下 之前已经标记的转弯次数 是比当前的大于等于吗 如果是 那么这个点 就可以继续走下去 如果不是 目前的这个状态就可以不要 相当于剪枝了
有几个坑点 输入的时候 坐标是从1-N 1-M 的
然后输入起始坐标的时候，， x 代表列 y 代表行
AC代码
#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<map> #include<set> #include<string> #include<list> #include<stack> #include <queue> #define CLR(a, b) memset(a, (b), sizeof(a)) using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int maxn = 1e2 + 5; int Move[4][2] = // up 0 down 1 left 2 right 3 { -1, 0, // up 1, 0, // down 0,-1, // left 0, 1, // right }; int n, m; int G[maxn][maxn]; int v[maxn][maxn]; int sx, sy, ex, ey, limit; int ans; struct node { int x, y; int step; int dis; }; bool ok(int x, int y, int step) { if (x < 0 || x >= n || y < 0 || y >= m || G[x][y] == 0 || v[x][y] < step) return false; return true; } void bfs() { queue <node> q; node tmp; tmp.step = 0; v[sx][sy] = 1; for (int i = 0; i < 4; i++) { tmp.x = sx + Move[i][0]; tmp.y = sy + Move[i][1]; tmp.dis = i; if (ok(tmp.x, tmp.y, tmp.step)) { q.push(tmp); v[tmp.x][tmp.y] = tmp.step; } } while (!q.empty()) { node u = q.front(), V; q.pop(); if (u.x == ex && u.y == ey) { if (u.step <= limit) { ans = 1; return; } } if (u.step > limit) continue; for (int i = 0; i < 4; i++) { V.x = u.x + Move[i][0]; V.y = u.y + Move[i][1]; if (u.dis != i) V.step = u.step + 1; else V.step = u.step; V.dis = i; if (ok(V.x, V.y, V.step)) { q.push(V); v[V.x][V.y] = V.step; } } } } void init() { CLR(G, 0); CLR(v, 0x3f); } int main() { int t; cin >> t; while (t--) { init(); scanf("%d%d", &n, &m); char c; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf(" %c", &c); if (c == '.') G[i][j] = 1; else G[i][j] = 0; } } scanf("%d%d%d%d%d", &limit, &sy, &sx, &ey, &ex); sx--, sy--, ex--, ey--; ans = 0; bfs(); if (ans) printf("yes\n"); else printf("no\n"); } }转载于:https://www.cnblogs.com/Dup4/p/9433105.html
