求助，70pts，悬关

FBI_Hu_Tao @ 2024-09-29 20:01:29

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,val,prex,prey;
    bool operator<(node x)const{
        return val>x.val;
    }
    bool operator>(node x)const{
        return val<x.val;
    }
};
const int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,sx,sy,ex,ey;
priority_queue<node> q;
int vis[114][114],dis[114][114];
char a[114][114];
void bfs(int sx,int sy){
    vis[sx][sy]=1;
    dis[sx][sy]=0;
    q.push(node{sx,sy,0,0,0});
    while(!q.empty()){
        node now=q.top();q.pop();
        for(int i=0;i<4;i++){
            int nx=now.x+d[i][0],ny=now.y+d[i][1];
            if(nx>0&&nx<=n&&ny>0&&ny<=n&&a[nx][ny]!='x'&&!vis[nx][ny]){
                int dist=0;
                if(now.prex==0&&now.prey==0)dist=0;
                else if(now.prex==now.x)dist=(nx!=now.prex);
                else if(now.prey==now.y)dist=(ny!=now.prey);
                if(dis[nx][ny]>=dis[now.x][now.y]+dist){
                    vis[nx][ny]=1;
                    dis[nx][ny]=dis[now.x][now.y]+dist;
                    q.push({nx,ny,dis[nx][ny],now.x,now.y});
                }
            }
        }
    }
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            if(a[i][j]=='A'){
                sx=i,sy=j;
            }else if(a[i][j]=='B'){
                ex=i,ey=j;
            }
        }
    }
    memset(dis,63,sizeof(dis));
    bfs(sx,sy);
    if(vis[ex][ey]==0)cout<<-1;
    else cout<<dis[ex][ey];
    return 0;
}

by Tepley @ 2024-10-02 21:45:03

我的做法和你的不太一样

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

const int N = 110;
int n, startx, starty, endx, endy, a[N][N], vis[N][N][5];
int disx[5] {0,0,0,-1,1}, disy[5] {0,1,-1,0,0};
struct node{
    int x, y, change, flag;
    bool operator < (const node &b) const{
        return change > b.change;
    }
};

inline void bfs()
{
    priority_queue <node> q;
    vis[startx][starty][1] = vis[startx][starty][2] = vis[startx][starty][3] = vis[startx][starty][4] = 1;
    q.push({startx,starty, 0, 1});
    q.push({startx,starty, 0, 2});
    q.push({startx,starty, 0, 3});
    q.push({startx,starty, 0, 4});
    while (!q.empty())
    {
        node tmp = q.top();
        q.pop();
        for (int i = 1; i <= 4; i ++)
        {
            int xi = tmp.x + disx[i], yi = tmp.y + disy[i];
            int flagi = i,changei = (tmp.flag == i ? tmp.change : tmp.change + 1);
            while (xi <= n && xi >= 1 && yi <= n && yi >= 1 && !a[xi][yi] && !vis[xi][yi][flagi])
            {
                vis[xi][yi][flagi] = 1;
                q.push({xi, yi, changei, flagi});
                if (xi == endx && yi == endy) {
                    cout << changei - 1;
                    exit(0);
                }
                xi += disx[i];
                yi += disy[i];
            }
        }
    }
    return;
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= n; j ++)
        {
            char x;
            cin >> x;
            if (x == 'x') a[i][j] = 1;
            else if (x == 'A') startx = i, starty = j;
            else if (x == 'B') endx = i, endy = j;
        }
    }
    bfs();
    cout << "-1";
    return 0;
}