AcWing 175. 电路维修

对于路径值都是0或1是，用双端队列宽搜，值为0的点加入对头优先遍历，值为1的点加入队尾后遍历，保证单调性

#include
using namespace std;

typedef pair PII;
const int N = 550;
char g[N][N];
int T,n,m;
int d[N][N];
deque q;

int dx[]={-1,0,0,1,-1,-1,1,1},dy[]={0,-1,1,0,-1,1,-1,1};

int bfs(int x,int y)
{
    memset(d,0,sizeof d);
    q.clear();
    d[x][y]=1;    
    if(g[x][y]=='/')g[x][y]='\',d[x][y]++;
    q.push_front({x,y});
    while(!q.empty())
    {
        auto t=q.front();
        q.pop_front();
        if(t.first==n-1&&t.second==m-1)return d[t.first][t.second]-1;
        for(int i=0;i<8;i++)
        {
            int vx=t.first+dx[i],vy=t.second+dy[i];
            if(vx<0||vx>=n||vy<0||vy>=m||d[vx][vy])continue;
            if(i<4&&g[vx][vy]!=g[t.first][t.second])
            {
                d[vx][vy]=d[t.first][t.second];
                q.push_front({vx,vy});
            }
            else if(i<4&&g[vx][vy]==g[t.first][t.second])
            {
                if(g[t.first][t.second]!='/')g[vx][vy]='/';
                else g[vx][vy]='\';
                d[vx][vy]=d[t.first][t.second]+1;
                q.push_back({vx,vy});
            }
            else if((i==4||i==7)&&g[t.first][t.second]=='\'
            &&g[vx][vy]==g[t.first][t.second])
            {
                d[vx][vy]=d[t.first][t.second];
                q.push_front({vx,vy});
            }
            else if((i==4||i==7)&&g[t.first][t.second]=='\'
            &&g[vx][vy]!=g[t.first][t.second])
            {
                g[vx][vy]='\';
                d[vx][vy]=d[t.first][t.second]+1;
                q.push_back({vx,vy});
            }
            else if((i==5||i==6)&&g[t.first][t.second]=='/'
            &&g[vx][vy]==g[t.first][t.second])
            {
                d[vx][vy]=d[t.first][t.second];
                q.push_front({vx,vy});
            }
            else if((i==5||i==6)&&g[t.first][t.second]=='/'
            &&g[vx][vy]!=g[t.first][t.second])
            {
                g[vx][vy]='/';
                d[vx][vy]=d[t.first][t.second]+1;
                q.push_back({vx,vy});
            }
        }
    }
}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0;i