题解 | PUBG

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

int n;
int sx,sy,ex,ey;
int mp[110][110];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int dist[110][110];
bool st[110][110];
struct node{
    
    int x;
    int y;
    int num;
//     node(int x,int y,int num)
//     {
//         x=this->x;
//         y=this->y;
//         num=this->num;
//     }
   
};

struct cmp
{
     bool operator()(  node a , node b)
    {
        return a.num>b.num;
    }
};
// bool cmp(node a,node b)
// {
//     return a.num<b.num;
// }

int spfa()
{
//     cout<<sx<<" "<<sy<<endl;
    priority_queue<node,vector<node>,cmp> heap;
//     if(heap.empty()) cout<<"ok"<<endl;
//     heap.push({sx,sy,0});
    node pp ;
    pp.x=sx,pp.y=sy;pp.num=0;
//     cout<<pp.x<<" "<<pp.y<<" "<<pp.num<<endl;
    heap.push(pp);
//     if(!heap.empty()) cout<<"ok"<<endl;
//     cout<<sx<<" "<<sy<<endl;
//     st[sx][sy]=true;
//     node t=heap.top();
//     cout<<t.x<<" "<<t.y<<" "<<t.num<<endl;
    while(!heap.empty())
    {
        node  t=heap.top();
        
        int dis=t.num;
        int x=t.x;
        int y=t.y;
//         cout<<x<<" "<<y<<" "<<dis<<endl;
        heap.pop();
        if(st[x][y]) continue;
        st[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i],yy=y+dy[i];
           
            if(xx==sx&&yy==sy) continue;
            if(xx==ex&&yy==ey)
            { 
                dist[ex][ey]=min(dist[ex][ey],dis);
                continue;
            }
//              cout<<xx<<" "<<yy<<" "<<dist[xx][yy]<<" "<<mp[xx][yy]<<endl;
            if(xx>=1&&xx<=n&&yy>=1&&yy<=n)
            {
                if(dist[xx][yy]>dis+mp[xx][yy])
                {
                    dist[xx][yy]=dis+mp[xx][yy];
                  
                     heap.push({xx,yy,dist[xx][yy]});
                        
                    
                }
            }
        }
    }
    return dist[ex][ey];
}
void sc()
{
    memset(dist,0x3f,sizeof dist);
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            st[i][j]=false;
            cin>>mp[i][j];
            if(mp[i][j]==-1) 
            {
                sx=i,sy=j;
            }
            else if (mp[i][j]==-2)
            {
                ex=i,ey=j;
            }
        }
//     cout<<sx<<" "<<sy<<" "<<ex<<" "<<ey<<endl;
    int sum=spfa();
    cout<<sum<<endl;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        sc();
    }
}