题目描述：
同学们在教室坐好，准备去郊游，他们依次离开教室。同学们的座位由一个 n \times n 的矩阵表示，左上角为下标 (1,1) 的同学，右下角为 (n,n) ，而且座位编号是从左上角到右下角一排排一列列编号的，分别为 1、2、3、4…… n^2 。第i个离开教室的同学的初始座位是 a_i 。当前走动的同学可以从当前位置移动到其上下左右 4 个相邻座位之一，当他走到一个非空的座位时会和坐在这个位置上的同学成为好朋友，每个同学都会选择结交最少好朋友的走法离开教室。计算所有好朋友对 (i,j) 的数量 (i≠j) 。
输入格式：
第一行包含一个整数 n ，表示矩阵大小。
接下来一行包含 n \times 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 \le n \le 500 ， 1 \le a_i \le n \times 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号座位离开教室。
题意+思路
这道题就是一个二维矩阵，按照给定顺序走，第 i 次走编号 a_i 的同学，问最少经过几个同学。老师讲的思路是bfs+中转站思路。但是我是用dfs做的：
-
用 vis 数组记录访问过的位置， use[i] 记录 i 位置的学生是否已经出去，出去为 0 ，还没出去为 1 。 dp[i][j] 表示 (i,j) 到边界经过的学生的最小值。
初始时 dp[i][j]=min({i-1,j-1,n-i,n-j}) ，即 (i,j) 到边界的最短距离。 -
dfs思路：若 dp[nx][ny] > dp[x][y] + use[x][y] ，则 dp[nx][ny] 就可以被改为 dp[x][y]+use[x][y] ，这样答案就会更小， dfs(nx,ny) 就会划算。
-
细节：将编号转为坐标。设左上角为 (1,1) ，右下角为 (n,n) ，可以得到
x=\frac{a[i][j]+n-1}{n}，y=a[i][j]-(x-1) \times n 。
{x,y} 处的答案就是 dp[x][y] 。最后的结果就是每一处的答案之和。 -
时间复杂度：两重循环+二维memset初始化 O(n^4)
AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long //个人习惯
int n,ans=0;
bool use[505][505],vis[505][505];
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int dp[505][505],a[505][505];
void dfs(int x,int y){
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&!vis[nx][ny]){
if(dp[nx][ny]>dp[x][y]+use[x][y]){ //判断是否更小
vis[nx][ny]=1;
dp[nx][ny]=dp[x][y]+use[x][y]; //更新答案
dfs(nx,ny);
vis[nx][ny]=0;
}
}
}
}
signed main(){
cin>>n;
memset(use,1,sizeof(use));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j]=min(min(i-1,j-1),min(n-i,n-j)); //dp初始化
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
memset(vis,0,sizeof(vis));
int x=(a[i][j]+n-1)/n,y=a[i][j]-(x-1)*n; //计算坐标
ans+=dp[x][y]; //答案加起来
use[x][y]=0; //走掉了
vis[x][y]=1;
dfs(x,y);
}
}
cout<<ans<<endl;
return 0;
}