spfa,但是30分

f（flag）用来判断转向

#include<iostream>
#include<queue>
#include<algorithm>
#include<string.h>

using namespace std;
const int N = 1e2+7;
typedef pair<int,int> PII;
int n;
int g[N][N];
int dis[N][N];
int idx[N][N];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int x1,x2,y1,y2;
void spfa()
{
    memset(dis,0x3f,sizeof dis);
    dis[x1][y1]=0;
    idx[x1][y1]=1;
    queue<PII> q;
    queue<int> f;//1竖着走，0横着走 
    q.push({x1,y1});
    f.push(2);
    while(!q.empty())
    {
        int x=q.front().first;
        int y=q.front().second;
        //cout<<x<<' '<<y<<endl;
        int flag=f.front();
        idx[x][y]=0;
        q.pop();
        f.pop();
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            //cout<<xx<<' '<<yy<<endl; 
            int now=0,flg;
            if(xx<1||xx>n||yy<1||yy>n) continue;
            if(g[xx][yy]==0) continue;
            if(flag==0)
            {
                if(abs(dx[i])==1)
                {
                    now=1;
                    flg=1;
                }
                else flg=0;
            } 
            if(flag==1)
            {
                if(abs(dy[i])==1)
                {
                    now=1;
                    flg=0;
                }
                else flg=1;
            } 
            if(flag==2)
            {
                if(abs(dx[i])==1) flg=1;
                else flg=0;
            }
            if(dis[xx][yy]>dis[x][y]+now)
            {
                dis[xx][yy]=dis[x][y]+now;
                if(idx[xx][yy]==0)
                {
                    idx[xx][yy]=1;
                    q.push({xx,yy});
                    f.push({flg});
                }
            }
        }
    }
};

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            char s;
            cin>>s;
            if(s=='x') g[i][j]=0;
            else if(s=='.') g[i][j]=1;
            else if(s=='A')
            {
                x1=i,y1=j;
                g[i][j]=2;
            }
            else
            {
                x2=i,y2=j;
                g[i][j]=2;
            }
        }
    }
    //for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cout<<g[i][j]<<" \n"[j==n];
    //cout<<x1<<' '<<y1<<endl<<x2<<' '<<y2<<endl; 
    spfa();
    cout<<dis[x2][y2];
    return 0;
}

其实我发现

if(dis[xx][yy]>dis[x][y]+now)

有问题，在某些情况下后出现的相等的却更优，但改为

if(dis[xx][yy]>=dis[x][y]+now)

却会死循环

于是我就突发奇想

#include<iostream>
#include<queue>
#include<algorithm>
#include<string.h>

using namespace std;
const int N = 1e2+7;
typedef pair<int,int> PII;
int n;
int id;
int g[N][N];
int dis[N][N];
int idx[N][N];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int x1,x2,y1,y2;
void spfa()
{
    memset(dis,0x3f,sizeof dis);
    dis[x1][y1]=0;
    idx[x1][y1]=1;
    queue<PII> q;
    queue<int> f;//1竖着走，0横着走 
    q.push({x1,y1});
    f.push(2);
    int cnt = 0;
    while(!q.empty())
    {
        int x=q.front().first;
        int y=q.front().second;
        //cout<<x<<' '<<y<<endl;
        if(x==x2 && y==y2)
        {
            cnt++;
            if(cnt==n*n-id)
                return;
        }
        int flag=f.front();
        idx[x][y]=0;
        q.pop();
        f.pop();
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            //cout<<xx<<' '<<yy<<endl; 
            int now=0,flg;
            if(xx<1||xx>n||yy<1||yy>n) continue;
            if(g[xx][yy]==0) continue;
            if(flag==0)
            {
                if(abs(dx[i])==1)
                {
                    now=1;
                    flg=1;
                }
                else flg=0;
            } 
            if(flag==1)
            {
                if(abs(dy[i])==1)
                {
                    now=1;
                    flg=0;
                }
                else flg=1;
            } 
            if(flag==2)
            {
                if(abs(dx[i])==1) flg=1;
                else flg=0;
            }
            if(dis[xx][yy]>=dis[x][y]+now)
            {
                dis[xx][yy]=dis[x][y]+now;
                if(idx[xx][yy]==0)
                {
                    idx[xx][yy]=1;
                    q.push({xx,yy});
                    f.push({flg});
                }
            }
        }
    }
};

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            char s;
            cin>>s;
            if(s=='x')
            {
                g[i][j]=0;
                id++;
            }
            else if(s=='.') g[i][j]=1;
            else if(s=='A')
            {
                x1=i,y1=j;
                g[i][j]=2;
            }
            else
            {
                x2=i,y2=j;
                g[i][j]=2;
            }
        }
    }
    spfa();
//  for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cout<<(dis[i][j]==0x3f3f3f3f?-1:dis[i][j])<<" \n"[j==n];
//  cout<<x1<<' '<<y1<<endl<<x2<<' '<<y2<<endl; 
    cout<<dis[x2][y2];
    return 0;
}

结果得了60分