双向bfs wa5个点 已经打上注释dalao们看看啊呜呜呜

P1746 离开中山路

阿尔托莉雅丶 @ 2020-12-09 16:57:28

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int offx[4] = {1, 0, -1, 0};
int offy[4] = {0, 1, 0, -1};
int sx, sy, ex, ey;
int n;
int map[1005][1005];

int dbfs(int sx, int sy, int ex, int ey) //sx表示startx,ex表示endx
{
    queue<int> qs;
    queue<int> qe;
    int steps = 0, stepe = 0;

    qs.push(sx);   //首个点入队
    qs.push(sy);
    qs.push(steps);
    map[sy][sx] = 2; //首个标记一下
    qe.push(ex);
    qe.push(ey);
    qe.push(stepe);
    map[ex][ey] = 3;

    while(!qs.empty() && !qe.empty())
    {
        if(qs.size() <= qe.size()) //优先搜少的那边
        {
            sx = qs.front();  //出队
            qs.pop();
            sy = qs.front();
            qs.pop();
            steps = qs.front();
            qs.pop();
            steps++;  //步数加一
            for(int i = 0; i < 4; i++)
            {
                int dx = sx + offx[i];
                int dy = sy + offy[i];

                if(dy >= 0 && dx >= 0 && map[dy][dx] == 3) //如过重合了就返回step和
                    return stepe + steps;

                if(dx >= 0 && dx < n && dy >= 0 && dy < n && map[dy][dx] == 0)
                {
                    qs.push(dx);
                    qs.push(dy);
                    qs.push(steps);

                    map[dy][dx] = 2;
                }
            }
        }
        else  //反向搜同理
        {
            ex = qe.front();
            qe.pop();
            ey = qe.front();
            qe.pop();
            stepe = qe.front();
            qe.pop();
            stepe++;
            for(int i = 0; i < 4; i++)
            {
                int dx = ex + offx[i];
                int dy = ey + offy[i];

                if(dy >= 0 && dx >= 0 && map[dy][dx] == 2) //溢出
                    return stepe + steps;

                if(dx >= 0 && dx < n && dy >= 0 && dy < n && map[dy][dx] == 0)
                {
                    qe.push(dx);
                    qe.push(dy);
                    qe.push(stepe);

                    map[dy][dx] = 3;
                }
            }
        }
    }

    return -1;

}

int main(void)
{
    cin >> n;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
            scanf("%1d", &map[i][j]);
    }

    cin >> sx >> sy >> ex >> ey;

       cout<<dbfs(sx - 1, sy - 1, ex - 1, ey - 1); //从零开始下标
    return 0;
}

|