字母迷宫题解

思路：

看到这题一眼跑广搜，但是转眼天堂之门，欸为什么要加2？

好像没法广搜（不满足广搜特性），咋办？凉拌。

该怎么让它满足广搜特性（先搜到的是最优的）。

欸，我们是不是可以将队列换成优先队列让先搜到的最优。好像是的欸，优先队列启动！

代码：

#include<bits/stdc++.h>
using namespace std;
int ans[1210][1210],nxt[4][2]={1,0,0,1,-1,0,0,-1},nxt1[4][2]={2,0,0,2,-2,0,0,-2},nxt2[4][2]={1,1,1,-1,-1,-1,-1,1},n;
char maps[1210][1210];
struct node{
    int x,y,step;
    friend bool operator<(const node X,const node Y){
        return X.step>Y.step;
    }
};
void bfs(){
    priority_queue<node> que;
    if(maps[1][1]!='*') que.push({1,1,1}),ans[1][1]=1;
    if(maps[1][n]!='*') que.push({1,n,1}),ans[1][n]=1;
    if(maps[n][1]!='*') que.push({n,1,1}),ans[n][1]=1;
    while(!que.empty()){
        node Now=que.top();
        que.pop();
        if(Now.x==n&&Now.y==n){
            cout<<Now.step;
            exit(0);
        }
        if(maps[Now.x][Now.y]=='A'){
            for(int i=0;i<4;i++){
                node Next=Now;
                Next.x+=nxt[i][0];
                Next.y+=nxt[i][1];
                Next.step++;
                if(Next.x>=1&&Next.x<=n&&Next.y>=1&&Next.y<=n&&Next.step<ans[Next.x][Next.y]&&maps[Next.x][Next.y]!='*'){
                    ans[Next.x][Next.y]=Next.step;
                    que.push(Next);
                }
            }
        }else if(maps[Now.x][Now.y]=='B'){
            for(int i=0;i<4;i++){
                node Next=Now;
                Next.x+=nxt1[i][0];
                Next.y+=nxt1[i][1];
                Next.step++;
                if(Next.x>=1&&Next.x<=n&&Next.y>=1&&Next.y<=n&&Next.step<ans[Next.x][Next.y]&&maps[Next.x][Next.y]!='*'){
                    ans[Next.x][Next.y]=Next.step;
                    que.push(Next);
                }
            }
        }else{
            for(int i=0;i<4;i++){
                node Next=Now;
                Next.x+=nxt2[i][0];
                Next.y+=nxt2[i][1];
                Next.step+=2;
                if(Next.x>=1&&Next.x<=n&&Next.y>=1&&Next.y<=n&&Next.step<ans[Next.x][Next.y]&&maps[Next.x][Next.y]!='*'){
                    ans[Next.x][Next.y]=Next.step;
                    que.push(Next);
                }
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ans[i][j]=1e9;
            cin>>maps[i][j];
        }
    }
    bfs();
    cout<<"No answer";
}