附一张关于dx,dy,ix,iy解析的图
(图片来自另一份题解:[https://www.acwing.com/solution/content/21775/])
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=510;
int n,m;
char g[N][N];
int d[N][N];
bool v[N][N];
deque<PII> q;
/*STL提供的双端队列
常用操作有:
1 front/back: 队头/队尾元素值
2 push_front: 从队头入队
3 push_back: 从队尾入队
4 pop_front: 从队头出队
5 pop_back: 从队尾出队
6 clear: 清空队列
*/
int bfs()
{
memset(v,0,sizeof(v));
memset(d,0x3f,sizeof(d));
//下标从(0,0)开始
q.push_front({0, 0});
d[0][0] = 0;
int dx[4] = {-1, -1, 1, 1}; //dx[]和dy[]表示可以去其他点的方向
int dy[4] = {-1, 1, 1, -1};
int ix[4] = {-1, -1, 0, 0}; //id[]和iy[]表示需要踩某个方向的格子才能去到相应的点
int iy[4] = {-1, 0, 0, -1};
char cs[] = "\\/\\/"; //cs[]表示当前点走到4个方向的点理想状态下格子形状(边权是0的状态)
while (q.size())
{
auto t = q.front();
q.pop_front();
int x = t.first, y = t.second;
//控制每个点只出队一次
if (v[x][y]) continue;
else v[x][y] = 1;
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i]; //(a,b)代表走到的点的坐标
int j = x + ix[i], k = y + iy[i]; //(j,k)代表格子
if (a >= 0 && a <= n && b >= 0 && b <= m) //边界判断
{
int w = 0;
if (g[j][k] != cs[i]) w = 1; //cs[]是理想状态,若不是cs就需要旋转
if (d[a][b] > d[x][y] + w)
{
d[a][b] = d[x][y] + w;
//若拓展某一元素的边权是0,则将该元素插入到队头
//若拓展某一元素的边权是1,则将该元素插入到队尾
if(w) q.push_back({a, b});
else q.push_front({a, b});
}
}
}
}
if(d[n][m]==0x3f3f3f3f) return -1;
else return d[n][m];
}
int main()
{
int T;cin>>T;
while (T--)
{
cin>>n>>m;
for (int i=0; i<n;i++ )
for(int j=0;j<m;j++)
cin>>g[i][j];
int t = bfs();
if(t==-1) puts("NO SOLUTION");
else cout<<t<<endl;
}
return 0;
}