时间：3s 空间：256M 题目描述：

同学们在教室坐好，准备去郊游，他们依次离开教室。同学们的座位由一个n×n的矩阵表示，左上角为下标 (1,1) 的同学，右下角为(n,n)，而且座位编号是从左上角到右下角一排排一列列编号的，分别为 1、2、3、4…… n2 。第i个离开教室的同学的初始座位是ai。当前走动的同学可以从当前位置移动到其上下左右4个相邻座位之一，当他走到一个非空的座位时会和坐在这个位置上的同学成为好朋友，每个同学都会选择结交最少好朋友的走法离开教室。计算所有好朋友对(i,j)的数量(i≠j)。 输入格式：

第一行包含一个整数 n，表示矩阵大小。

接下来一行包含 n×n 个整数，表示依次离开的同学的初始座位 。

输出格式：

输出一个整数表示答案。

样例1输入：

3 5 2 4 6 8 1 3 7 9

样例1输出：

1

样例2输入：

3 2 5 4 6 8 1 3 7 9

样例2输出：

0

样例3输入：

4 6 7 1 4 13 16 10 9 5 11 12 14 15 2 3 8

样例3输出：

3

约定与提示：

对于100%的数据，2≤n≤500，1≤ai≤n×n)

样例1和2的座位如图：

1 2 3 4 5 6 7 8 9

样例1解释：坐在5号座位的同学先离开教室，他必须经过1，2，3，4，6，7，8，9座位中的一个，所以他必须跟其中1个同学成为朋友。

样例2解释：坐在2号座位的同学先离开教室，接着坐在5号座位的同学离开，他可以经过2号座位离开教室。

样例3的座位如图：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 我的代码

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,step[505][505],ID,ans,vis[505][505],tx[10]={0,0,1,-1},ty[10]={1,-1,0,0};
void update(int x,int y)
{
	for(int i=0;i<4;i++)
	{
		int dx=x+tx[i];
		int dy=y+ty[i];
		if(step[dx][dy]>vis[x][y]+step[x][y])
		{
			step[dx][dy]=vis[x][y]+step[x][y];
			update(dx,dy);
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			step[i][j]=min(min(i,n-i+1),min(j,n-j+1))-1;
			vis[i][j]=1;
		 } 
	}
	for(int i=1;i<=n*n;i++)
	{
		cin>>ID;
		int x=(ID+n+1)/n;
		int y=ID%n?ID%n:n;
		ans+=step[x][y];
		vis[x][y]=0;
		update(x,y);
	}
	cout<<ans;
	return 0;
}

蒟蒻求助