[AcWing] 双端队列广搜 175. 电路维修

175. 电路维修 题意:

就是给你一个电路板, 里面的电线都是斜着的\ 或者 / 你可以旋转这个 让你连通左上角和右下角, 问你旋转的最小步数(鳄鱼洗澡?)

问题转换

把能走通的两个端点之间 看作边权为0 否则看作边权为1

思维:

我们把所有点的横纵坐标加一下 因为起点一直都是偶数点 偶数点只能到偶数点 如果是偶数点那么是一定能到的,否则一定不能到

区别1

因为只存在0,1两种 如果我们扩展到0的话 0放队头 如果我们拓展到1的话 1放队尾 后面和bfs一样的

为什么可以这样呢

因为队列满足 两段且单调

区别2

之前的因为边权都是相等的 所以只会入队一次 而这种和dij一样 素以我们可能会入队多次 因此我们需要判重

code:

#include 
using namespace std;
struct node
{
    int x,y;
};
const int N = 510 ,M = N*N;
int n,m;
char g[N][N];
int st[N][N];
int dist[N][N];
int bfs()
{
    memset(dist,0x3f,sizeof  dist);
    memset(st,0,sizeof st);
    dist[0][0]= 0;///这个是点的下标

    deque q;///定义双端队列
    q.push_back({0,0});
    char cs[] ="\\/\\/";///是否移动
    ///因为只能动偶数点
    int dx[4] = {-1,-1,1,1},dy[4] ={-1,1,1,-1};
    int ix[4] = {-1,-1,0,0},iy[4] ={-1,0,0,-1};
    ///表示的是 字符所在的格子的移动

    while(!q.empty())
    {
        node t = q.front();
        q.pop_front();
        if(st[t.x][t.y]) continue;
        st[t.x][t.y] = 1;
        for(int i=0;it;
    while(t -- )
    {
        cin>>n>>m;
        for(int i=0;i>g[i];
        int t =bfs();
        if(t == 0x3f3f3f3f)
            cout