本题思路:
所谓求讨厌关系其实就是转换成了出去要多少步(碰到人了才算)
而本题的精髓就在于:
由一个点延展出来的格子的最短距离不可能比该点的最短距离+1还要大
因为有这个点延展出来的格子都能通过先走到这个点再依据这个点的最短路径出去
题目描述
(中文翻译版)
交大教室里由n排座位,每排有n个座位,形成了一个nn的矩阵。今天,教室里意外地坐满了人。我们可以认为,第1,2,…,n位学生从左至右依次坐在第一排的座位,第n+1,n+2,…,n+n位学生坐在第二排地位置,第nn-n+1,nn-n+2,…,nn位学生坐在最后一排地座位上。
下课后,教室里的nn个学生会按照一个固定的顺序P离开教室。学生Pi+1必须等待Pi离开教室后,他才能离开教室。学生离开教室时,必须一个一个座位地移动,直到从nn个座位形成地矩阵边缘离开。(可以从矩阵四条边中地任意一条离开)。学生可以从当前的椅子移动到上下左右相邻的四个椅子。如果学生x在离开教室的过程中,经过一个坐着学生y的椅子(即学生x离开教室时,学生y尚未离开教室),则学生y会非常讨厌学生x。
现在,给定学生离开的顺序P。求最少有多少对讨厌关系。
Constraints
2 ≤ n ≤ 500
序列P1,P2,…,Pnn是一个1..nn的排列
Input
第一行,一个整数n,表示座位矩阵的边长。
第二行,一个长度为n*n的序列P,表示出教室的顺序
Output
一行一个整数,表示按顺序P离开时最少有多少组讨厌关系。
样例
Sample Input 1
3
9 7 3 1 5 6 8 4 2
Sample Output 1
1
一开始,所有学生都坐在座位上:
1 2 3
4 5 6
7 8 9
前四个离开教室的人9,3,7,1,都可以直接从边缘离开。
然后,对于5号学生,他想要离开教室,必须经过2,4,6,8中的一个座位,而当前这四张座位上的学生都没有离开,所以5号学生至少被2,4,6,8中的一个人讨厌。
最后,6,8,4,2号学生直接从教室边缘离开。
Sample Input 2
4
6 7 1 4 13 16 10 9 5 11 12 14 15 2 3 8
Sample Output 2
3
Sample Input 3
6
11 21 35 22 7 36 27 34 8 20 15 13 16 1 24 3 2 17 26 9 18 32 31 23 19 14 4 25 10 29 28 33 12 6 5 30
Sample Output 3
11
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int x[N*N], y[N*N];
int n;
int d[N][N];
bool del[N][N];
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
//延展(x,y)的四个方向上的格子
void extend(int x,int y)
{
for(int i=0;i<4;i++)
{
int nx=x+dx[i], ny=y+dy[i];
int nd=d[x][y]+1-del[nx][ny];
if(d[nx][ny]>nd)
{
d[nx][ny]=nd;
extend(nx,ny);
}
}
}
int main()
{
cin >> n;//边长
for(int i=1;i<=n*n;i++)
{
int p;
scanf("%d",&p);
//将出场顺序转换为教室的位置
x[i] = (p+n-1)/n;//(注意 / 是往下取整因此加上n-1)
y[i] = p-(x[i]-1)*n;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(min(i,j),min(n-i+1,n-j+1));//枚举东南西北的最短距离ex. d[1][1]=d[1][2]=d[1][3]=d[2][1]=d[2][3]
//=d[3][1]=d[3][2]=d[3][3]=1 d[2][2]=2
int ans=0;
//由一个点延展出来的格子的最短距离不可能比该点的最短距离+1还要大
//因为有这个点延展出来的格子都能通过先走到这个点再依据这个点的最短路径出去
for(int i=1;i<=n*n;i++)
{
ans+=d[x[i]][y[i]]-1;//记得减一
del[x[i]][y[i]]=1;
for(int j=0;j<4;j++)
{
int nx=x[i]+dx[j],ny=y[i]+dy[j];
d[x[i]][y[i]] = min(d[x[i]][y[i]], d[nx][ny]);
}
extend(x[i],y[i]);
}
cout << ans << endl;
}