题解：P10234 [yLCPC2024] B. 找机厅

· · 题解

看到“最短用时”，第一时间想到 bfs。

bfs 大部分应该都会写，所以主要难点在求路径。我们可以用 pair 或者结构体存一个坐标，然后存每个点的前缀，最后用栈从最后倒推输出就行了。这里存前缀可以直接用二维数组或者用 map。

很丑的赛时代码：

/*
皇帝的新缺省源
*/
struct pos//这里采用结构体存坐标
{
    int x,y;
    pos(){}
    pos(int _x,int _y):x(_x),y(_y){}//构造函数，冒号后面的就与 x=_x,y=_y 等价
};
bool operator==(pos _x,pos _y){return _x.x==_y.x&&_x.y==_y.y;}
bool operator!=(pos _x,pos _y){return !(_x==_y);}
const int _mxn=2e3+5;
pos pre[_mxn][_mxn];//存前缀的数组
int n,m,a[_mxn][_mxn];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
bool vis[_mxn][_mxn];
int as;
void bfs(int sx,int sy)//正式开始搜索
{
    queue<pos> q;
    pos nw(sx,sy);
    q.push(nw),vis[nw.x][nw.y]=true;
    while(!q.empty())
    {
        nw=q.front();q.pop();
        if(nw==pos(n,m))//到了
        {
            stack<pos> path;//栈存路径
            path.push(nw);
            while(nw!=pos(1,1))//往前推
            {
                nw=pre[nw.x][nw.y];
                path.push(nw);
            }
            cout<<path.size()-1<<endl;//输出时间
            int x,y;
            int tx=path.top().x,ty=path.top().y;path.pop();
            while(!path.empty())//输出路径
            {
                x=tx,y=ty;
                tx=path.top().x,ty=path.top().y;path.pop();
                if(pos(x-1,y)==pos(tx,ty))
                    cout<<"U";
                if(pos(x+1,y)==pos(tx,ty))
                    cout<<"D";
                if(pos(x,y-1)==pos(tx,ty))
                    cout<<"L";
                if(pos(x,y+1)==pos(tx,ty))
                    cout<<"R";
            }
            cout<<endl;
            return;
        }
        for(int i=0;i<4;i++)//遍历四个方向
        {
            pos nx(nw.x+dx[i],nw.y+dy[i]);
            if(nx.x<1||nx.x>n||nx.y<1||nx.y>m)//越界
                continue;
            if(vis[nx.x][nx.y])//走过了
                continue;
            if(a[nw.x][nw.y]!=a[nx.x][nx.y])//俩格子不同
            {
                pre[nx.x][nx.y]=nw;//前缀存上
                q.push(nx),vis[nx.x][nx.y]=true;//进队列，标访问
            }
        }
    }
    cout<<-1<<endl;//到不了
}
int main()
{
    ___();
    int _;//数据组数
    cin>>_;
    while(_--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                char c;
                cin>>c;
                a[i][j]=c-'0';
                vis[i][j]=false;//一块直接初始化（多测不清零，爆零两行泪）
            }
        bfs(1,1);//开搜
    }
    return 0;//完美结束 QwQ
}

赛时交了 11 发才过（