//01权值的bfs用双端队列去维护,现在的dijk的堆优化会被卡住
#include<iostream>
#include<cstring>
#include<queue>
#include<unordered_map>
#include<algorithm>
using namespace std;
typedef pair<int,int> pii;
const int N=510;
char g[N][N];
int d[N][N];
bool st[N][N];
//d数组控制格点坐标,i数组通过当前格点坐标来控制导线的坐标
int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1},ix[]={-1,-1,0,0},iy[]={-1,0,0,-1};
int n,m,t;
int bfs()
{
memset(d,0x3f,sizeof d);
memset(st,0,sizeof st);
deque<pii> q; //双端左边0导线不动,右边1导线转一下
q.push_front({0,0});
d[0][0]=0;
char cs[]="\\/\\/";
/*
\/
/\ 这是标准状态,因为不可能存在又0又1的导线
*/
while(q.size())
{
pii t=q.front();
q.pop_front();
if(st[t.first][t.second] == true) continue; //当前格点被搜过直接continue掉
st[t.first][t.second]=true;
for(int i=0;i<4;i++)
{
int a=t.first+dx[i],b=t.second+dy[i];
if(a<0 || a>n || b<0 || b>m) continue; //格点比边数多1,所以这里是大于
int ca=t.first+ix[i],cb=t.second+iy[i]; //当前导线状态
int dist=d[t.first][t.second]+(g[ca][cb] != cs[i]);
if(dist<d[a][b])
{
d[a][b]=dist; //发现距离更小则更新(0x3f到具体值的更新,只会走一次)
if(g[ca][cb] != cs[i]) q.push_back({a,b}); //不同方向则权值为1插入队尾
else q.push_front({a,b}); //相同则权值为0插入队头
}
}
}
return d[n][m];
}
int main()
{
cin.tie(0);
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>g[i];
if((n+m) & 1) cout<<"NO SOLUTION"<<'\n'; //终点格点为奇数性质则无法到达(因为起点为偶点)
else
{
cout<<bfs()<<'\n';
}
}
return 0;
}
##太详细了,一看就懂
#爱了爱了
谢谢你的点赞和评论,我也爱你么么哒