https://www.acwing.com/problem/content/177/
双端队列BFS
#include <bits/stdc++.h> #define x first #define y second using namespace std; const int N = 600; using PPI = pair<int, int>; char tb[N][N]; //储存电线初始状态 int dis[N][N]; //储存起点到各点的距离 bool vis[N][N]; int m, n; void bfs() { deque<PPI> q; int mx[4] = { 1, -1, -1, 1}; int my[4] = { 1, -1, 1, -1}; //四个移动方向, 右下 左上 右上 左下 int cx[4] = { 0, -1, -1, 0}; int cy[4] = { 0, -1, 0, -1}; char wire[] = "\\\\//"; //电线的四种状态 memset(vis, false, sizeof vis); memset(dis, 0x3f, sizeof dis); dis[0][0] = 0; q.push_back({ 0, 0}); while (!q.empty()) { auto f = q.front(); q.pop_front(); if (vis[f.x][f.y]) continue; vis[f.x][f.y] = true; //出队时才能再设为不可访问 if (f.x == m and f.y == n) { cout << dis[m][n] << endl; return; } for (int i = 0; i < 4; i++) { int nx = f.x + mx[i], ny = f.y + my[i]; int use_x = f.x + cx[i], use_y = f.y + cy[i]; //现在在使用哪个格子的电线 if (nx >= 0 and nx < m + 1 and ny >= 0 and ny < n + 1) { int w = (tb[use_x][use_y] != wire[i]); //若不需要转动电线则边权为0, 否则边权为1 if (dis[nx][ny] <= dis[f.x][f.y] + w) continue; if (w) { //边权为1则尾插 dis[nx][ny] = dis[f.x][f.y] + w; q.push_back({ nx, ny}); } else { //头插 dis[nx][ny] = dis[f.x][f.y]; q.push_front({ nx, ny}); } } } } printf("NO SOLUTION\n"); } int main() { #ifndef ONLINE_JUDGE freopen("D:/VS CODE/C++/in.txt", "r", stdin); freopen("D:/VS CODE/C++/out.txt", "w", stdout); #endif int t; cin >> t; while (t--) { cin >> m >> n; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> tb[i][j]; } } if ((m + n) & 1) { //x y 和为奇数的点无法到达 printf("NO SOLUTION\n"); } else bfs(); } fclose(stdin); fclose(stdout); return 0; }