3675. 逃离迷宫

双端队列广搜（边权为0-1）， 等价于Dijkstra

#include 
#include 
#include using namespace std;const int N = 110, M = N * N * 4;int n, m, k;
int x1, y1, x2, y2;
char g[N][N];
int dist[N][N][4];
bool st[N][N][4];struct Node
{int x, y, d;
}q[M];int get(int x)
{return (x + M) % M;
}bool bfs()
{int hh = 0, tt = 0;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};memset(dist, 0x3f, sizeof dist);memset(st, false ,sizeof st);for(int i = 0; i < 4; i ++){q[tt ++] = {x1, y1, i};dist[x1][y1][i] = 0;}while(hh != tt){auto t = q[hh];hh = get(hh + 1);if(st[t.x][t.y][t.d]) continue;if(dist[t.x][t.y][t.d] > k) continue;if(t.x == x2 && t.y == y2) return true;st[t.x][t.y][t.d] = true;int distance = dist[t.x][t.y][t.d];for(int i = 0; i < 4; i ++){int a = dx[i] + t.x, b = t.y + dy[i];int w = t.d != i;if(a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.'){if(dist[a][b][i] > distance + w){dist[a][b][i] = distance + w;if(!w)  hh = get(hh - 1), q[hh] = {a, b, i}; // 0加队首， 1加队尾else q[tt] = {a, b, i}, tt = get(tt + 1);}}}}return false;}int main()
{int T;cin >> T;while(T --){cin >> n >> m;for(int i = 0; i < n; i ++)cin >> g[i];cin >> k >> y1 >> x1 >> y2 >> x2;x1 --, y1 --, x2 --, y2 --;if(bfs()) cout << "yes" << endl;else cout << "no" << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！