题解 | #PUBG#

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<int ,int > PII;

const int N = 110;

int n; 
int g[N][N];
int d[N][N];
int x1,x2,y11,y2;

int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1};

int bfs()
{
	queue<PII> q;
	
	q.push({x1,y11});
	
	memset(d,0x3f,sizeof d);
	
	d[x1][y11]=0;
	
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		
		for(int k=0;k<4;k++)
		{
			int a=t.first+dx[k];
			int b=t.second+dy[k];
			
			if(a<1||a>n||b<1||b>n) continue;
			
			if(d[a][b]>d[t.first][t.second]+g[a][b])
			{
				d[a][b]=d[t.first][t.second]+g[a][b];
				q.push({a,b});
			}
		}
	}	
	
	return d[x2][y2];
}


int main()
{
    while(cin>>n)
    {
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=n;j++)
    		{
    			cin>>g[i][j];
    			if(g[i][j]==-1) 
    			{
    				x1=i;
    				y11=j;
    				g[i][j]=0;
				}else if(g[i][j]==-2)
				{
					x2=i;
					y2=j;
					g[i][j]=0;
				}
			}
			
		cout<<bfs()<<'\n'; 
    }
    return 0;
}