算法介绍
\(bfs+\)双端队列是一种单源最短路算法，适用于边权为 \(0\) 或 \(1\) 的图中。时间复杂度为 \(O（n）\) 。
算法原理分析
算法的整体框架与普通 \(bfs\) 求最短路类似，只是根据边权做了分类讨论，如果边权为 \(1\)，则将邻居节点压到队列尾部，反之，压到队列首部。当每个节点第一次出队时，当前距离就是最短距离。
例题：[P4667 [BalticOI 2011 Day1] Switch the Lamp On 电路维修]([P4667 BalticOI 2011 Day1] Switch the Lamp On 电路维修 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
题目大意：本题可以建模成最短路问题，将转动次数看作边权。题目的时间限制为 \(150ms\)，而节点数为 \((n+1)*(m+1) \leq 251001\)。因此，必须使用时间复杂度为 \(O（n）\)的算法来解决。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 5, P = 13331;
struct node
{
int x, y, dis;
};
int mp[N][N];
int n, m, dis[N][N];
int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, -1, 1};
int cd[4][2] = {{-1, -1}, {-1, 0}, {0, -1}, {0, 0}};
int key[4] = {2, 1, 1, 2};
deque<node> dq;
int read_ch()
{
char c;
while ((c = getchar()) != '/' && c != '\\')
;
return c == '/' ? 1 : 2;
}
void solve()
{
int T = 1;
// cin>>T;
while (T--)
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
mp[i][j] = read_ch();
}
}
memset(dis, 0x3f, sizeof(dis));
dq.push_back({1, 1, 0});
dis[1][1] = 0;
while (!dq.empty())
{
int x = dq.front().x, y = dq.front().y, d = dq.front().dis;
dq.pop_front();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
int w = mp[x + cd[i][0]][y + cd[i][1]] != key[i];
if (nx && ny && nx <= n + 1 && ny <= m + 1 && d + w < dis[nx][ny])
{
dis[nx][ny] = d + w;
if (w == 0)
dq.push_front({nx, ny, dis[nx][ny]});
else
dq.push_back({nx, ny, dis[nx][ny]});
if (nx == n + 1 && ny == m + 1)
break;
}
}
}
if (dis[n + 1][m + 1] == 0x3f3f3f3f)
cout << "NO SOLUTION";
else
cout << dis[n + 1][m + 1];
}
}
int main()
{
solve();
return 0;
}