题解：题目描述指出，需要计算所有好朋友对(i,j)的数量(i≠j)，即计算每个同学离开教室后与其他同学成为好朋友的数量总和。
解题思路如下：
-
初始化矩阵
vis和矩阵e，其中vis用于记录每个同学离开教室后最短路径的值，e用于标记每个座位上是否有同学。 -
对于每个同学的初始座位，将其置为0，表示有同学占据。
-
对于每个同学离开教室的顺序，计算其初始座位的坐标
(x, y)：- 如果初始座位是n的倍数，则
x=a/n，y=n； - 否则，
x=a/n+1，y=a%n。
- 如果初始座位是n的倍数，则
-
将
(x, y)位置的e置为0，表示该位置没有同学。 -
使用广度优先搜索，从起始位置
(x, y)出发，计算到达每个位置(dx, dy)的最短路径，更新vis矩阵。 -
将
vis[x][y]累加到答案ans中。 -
输出答案
ans。
下面是相应的代码解答：
#include<bits/stdc++.h>//传统异能
using namespace std;
int vis[505][505],e[505][505],w[5]={-1,0,1,0},p[5]={0,-1,0,1},minn,ans=0,n;
void bfs(int x,int y)//可用bfs也可用dfs
{
queue<int> q;//bfs经典队列
q.push(x);//把当前坐标压入队列
q.push(y);
while(q.size()){
x=q.front(),q.pop();//每次取出队头
y=q.front(),q.pop();
for(int i=0;i<4;i++){//遍历4个方向
int dx=x+p[i],dy=y+w[i];//下一个格子
if(dx<1||dx>n||dy<1||dy>n) {//判断是否出教室
continue;
}
if(vis[dx][dy]>vis[x][y]+e[x][y]){
vis[dx][dy]=vis[x][y]+e[x][y];
q.push(dx),q.push(dy);
}
}
}
}
int main(){
int a=0;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
vis[i][j]=min(min(n-i,i-1),min(n-j,j-1));//初始化
e[i][j]=1;
}
}
for(int i=1;i<=n*n;i++){
cin>>a;
int x,y;
if(a%n==0){
x=a/n;
y=n;
}
else{
x=a/n+1;
y=a%n;
}
e[x][y]=0;
bfs(x,y);
ans+=vis[x][y];
}
cout<<ans;
return 0;
}
// ..:::::. .....ii:.
// ..:::::. :::.....:::::.
// ..:i77LLYvvr:.:::.:i1PdqSs7:....irv7vri:.
// .:ii7122uI1J7r:::r7Y1XPgggZZPUr:...::ir7r7ri:.
// ::ii:72PPSSUUJJLvvuUSI5IJrrL15bgE17ri::irrvvv77i:..
// iiii::LPK5UXSPPbPZPPqDQBgE5KU7i7vUSDX1jsr7rir7vLvL7i:...
// :ri::ivXEUUIPqbqPSI221KMBQMDZqbPj77v1IPIUUI1Jrii7rvvsJvi......
// i7i:i7XKUJXbbKqS2YLvJs5EBQBMgggPqSuLv1I1KUu2X5IvriirLYJYLi:......
// rrrrvubUL1dPPSX21YYLXbZDgMBQQQBQMXSujrLX2jSuuu5XqJ7ir7vvvv7ri:......
// :rir71X5LUPPU52IUULYjDBBRQgQBBBBBBBQP2sY7UPusIUJjSqq1s77rrrrrrii:....::...
// .:rir72U7LKqU121IUuYjUPQBBBBBBBQBQRbDgdIUusvPPusI2ssKKX11vv7rii:i::::..::.:..
// .iiii71Y7YbI1IS252UJuISqBBQZDDgbKuJv7rYYu1XuL1ZX1UK2ujS5IuuJuJjv7rr::::........
// .:iirv2vijPvu5K552UjII5SX52jJLY7rii:i:iirYI2IjUPdK522Juj5SSuuJISX12jsv7rr::......
// ...:i:iv5LivXs155IS521II212L7rririi:::::iiirLuISI1PddX511JjJ2IK22IbPPKqIIuuYvi:........
// .irrir2YiJdYY5qIS5XUU2IjujYrrii:i:::::::iir7s2S5Iqggd52jjYusuuIXbdgEdqP5IUUss7i:::::::.
// .rri7rvJ:7Zj75PqSIX5I2511J1v7rr:i::.:::::::ir7u1S5PDRDbXIuuJuj12q5KbdPqSIuuJjuuv7iiirii..
// :7vYvrvjriP1r5EPP2S25IX5Uj2jYrrii::::.::::::iirLU5PPZgRDZPqI52X5KXPqPXqXS11YsLsujLvrriii:.
// .r7sj1vrvUiuKsYZdE5jIKXX5XU1jJrrii::...:...:.::iirvIqdbggMgMDDdZbbdDdgbdPdKSUUJYvJsUus77rr:..
// r7:iv2Jv7usvIUYEggZIYKPPXSUUJJ7i::::..............:ivqdEZMgggMgRgMDgDMZZEggZSKIS22jjJ1UUv7rr::.
// ir.:v1uUJuJ11UsXgMgZ11KPqq52Juv:.:::.........::r7v7vsSqEZgDRMMDDgRggDgDgdEZDggqXXdqKuuYuIIs7rr:.
// ::.:vuI2U1uU22jIPMggP22dbEqq5S5ui:::::.....ivu1ZQBBBQBQQDMDRQQggdEEMgDDMggEEbDggPPPdPqIIs11SjL7r:
// ...:7sjS52Yu25U2XDggEPUKgRDgDgDQgd2vrr::.:ivIbPbdZS52XXK5qdDDMRQMMZEEZEgDRgMZdPDgZPPqddPSXII11Lvi:
// . .:772S2s15qS52PDgZZPEDQQRgMgRDRDEXJ7ri::rvUsv77::...:.::s5KSPEgDRggZgZgZgDgdEEZEdPbbEbPXqIIJv7i:.
// .:iv1Xu1XPKUUXPgZgEDgMbP5KXIj1jUUIj7::.::irr::.. ......:rJYvYU5PEgDgEDbZZMgZbddDbbbdbEqPXKIIvr:.
// .rr:. ..rvSPuIZKSuSPDDgZDDgqU7777i::iivvvr:.. .:iii::ivvjuIUUuU2j777YuSqZZgEEPZgMgDdZEdPbPEPbqPKKSUr: .
// .IuL7i .ij5KUPPS2SPDDZPZDgPILLvLLL7riirv77:. ..::iirQBgMBBBBBBBBg5vrrvL15dgRDdbDDgZDdEPEPdPPqPPESS2Li.
// s2sLr: :7J15SXu5KDdZEEDgPqSgQRQBBBQBXrrr:. ..:::7Euiirrrir7juYri:::ii7JSdRdZdDdEbZPdbdbdKPPDZKuSuv:.
// iJY7v7. :ij1UsYSEZgEEEPKDBBB27XQMPdP2::::. ......:i7vrrirrri:.... ..::i71KEMRMMZDbbqPPddEdgZDX25U7:
// .susYY: .:YXu1sPDZPdS215X57i:iirr7i:...:.. ........:::::::..... ....::7URBQRQgDqPqbbZdgDgZPIXu7:
// iL7L7r i2S2IKZPEKYrri:.:i7r7ri........ . ....... ... . . . ... ........rURRQQMDgbdbdPEEgDgPq5L:.
// .iii7i. 7XX2PPZgK:. . . .. .... ....... ... . . ..........rSMQBQRMQZPIXqEbgZE57.
// .ri7rr:. rUdPEgD: . .... .......... . . . ...........:UDQgEXqXKIIIKPbZgu.
// .ir7rii. :5gZQS ... ... .. ....... ... . . ........iuESvrrrvv7ruXX2qI.
// .777rrr: .1gQ2 ... . . ... .iii::ii. .......... ... ... ......:.:i5dY.:iiii:.:J1uIr
// rv7v77: .LQq. ....... ......rEBXJLuEBBBsv7:.....:.................:.i5Pr.:jXv:...rYvY.
// ..... :rLLvrr r5. ...........::::i2BBPJ2IPXdMDX7.....:::::::::::::.:...:.:i2Ir..JBbr...:i7.
// . . .... .r7Yv7r: :i.........:::::::.ii::ir7ri:i::......:::i::::::::::::.:.::i77..:uSXv:...:.
// . . . . ..:..ir7v77: .v:......::.:.:...... ..... . ......:::ii::::::::.:.:.:.::r:..iiiLv:..:.
// .... . .....:rir777r :j:......:::.:.:... .....::i:::::::::....::iii:::..i:....
// . ...: .....:rJL7v7vr .i:.....:.:.:.... .isK25KZPPdPJr:. ....:::::::::::.:.::::i::.........
// .. . .:. ..:v. .....iJDS2JJ7r ......:::.:.. 7gBBQRPZbLvZQQBBBMqKu7::::::::::::::.:.::77:........i.
// 2..... :7. . ..si .... vQdU1vri ....:.:.::::rZBBZ7r:..: ..iisZBBBEu:::::::::::::::::::7S57:. .7.
// sB ... .Y: ..72 ... PZ1vr:i. .:...:..:isdQBQRv::..:::::ii:::. ..:.:::::::::::::::LSuXdgPv:2Qi
// BQ ... :v.. ..rI. ...::. iKvi::::. .:.:.:.::777::..::.::::i::.........:..:::::::::i:::irsY7uBBBBBBs
// .BB: . . .r: ...:s:.:7i:.. .rr::::.P .:ri::iii::.. .:::::::.. ..::::::i:::i:::....:.:.::::::i:i:i:ii7rr:UBu uBI
// QBBB .... ::....:7:.:.... ....::rB: :2QBBQBQBBBBBBBBBBBBBi .:::::::.....::::iii:i:i::::::.:.....::::::i:iiiirrrii1Br IBv
// vBBBBU ......:...::7i. ..:::.... .bBBBBBQBBBQBBBQBBBBBQBQBQBDi.:::::.:.:.::iiiirirrri:::::.:.......::::::iirrriiir:XP. ZBBj
// :BBBBBQ: .....:: ..:ir..:rr7ri::.. vBBQBBBBBBBBBBBQBBBBBBBBBBBBi.:.:.:.::::::::::::::............::::::iiiivv7r:iiirqS BBBB7 . .
// .BBBQBQBB. .:::7v...:r7i.ir777rr::... rBBQBQBBBQBBBBBBBQBBBBBBBBBBu::.:............ . . ....::i:ri77JULii::iriv2 .BBRBB .:irvr.
// .BQBBBBBBBB..r7v11:irvvu1i:rrrrrrriii:: sBBQQBBBBBBBBBBBBBBBBQBBBBBBXi....... . ...:::ii77LsU2uii:i:ii:7B.YBBRBE ..:irsUr
// BBBQBBBBBBBQ..irvvri77vvSSJvsvJrii77vrr. 5BBBQBBBBBBBBBBBBBBBBBBBBBQBBQv:... . ..............::rrvL12IISIjr:::iiri:ZBBBBQBBd ...:iivL7.
// jBBBBBBBBQBBBg7iir2r.:rr7vDBBQBBB2i:r77rLsMBBQBBBBBBBQBBBQBBBQBBBBBQBQBBBd7:..........:::::::::::::i7sIIKSqXKIJriiiiiiiiDBBQBBQQBZ .::i7LJv:
// BBBBBBBBBBBBBBBBQBBBi:iirYZBBBBBBBBXLvJ5ZBBBQBBBBBBBBBQBBBBBQBBBBBBBQBBBQBgsri:::i:iiiirrrrv7v777vY5KbPPqqXK2jririii:rJgBBBBQBQBBB ..::iivjL:
// .BQBBBBBBBBBBBBBBBBBQBBQgQBBBBBBBBBBBBBBQBBBBBQBBBBBBBBBQBBBBBBBBBQBQBBBBBQRJsujvv777v7Lvss1jUj22KqbPPqPKPXK2j7r:i::rSgBBBBBBBQBQBB: ..:::irvi
// QBBBBBBBBBBBBBBQBBBQBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBQBQBBBQBBBBBBBQBQU7jU5II1UUSSS2S5KKqKbPPKPqPKPKX217i:::sqBBBBBBBBBBBQBBBE ..::rrrrjL
// iBBBBQBQBBBBBQBBBBBBBBBBBQBBBBBQBQBBBBBBBBBBBQBBBBBBBBBBBBBBBBBQBQgBBBBBBBQBB5v7LLusJsJJ12KqqqqKqKPKqXPqPXXULrrJXDBQBBBBBQBBBBBBBBBQBK .::iii7LU7.
// QBBBBBQBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBQBQBBBBBBBBBQBBBBBquQEZBQBBBBBBBBP77r77vvY77vjIKXX5KSqXqKPXPSI1KdQBBBBBBBBBBBBQBBBBBBBQBQBb ..::iirvj:
// ZBBBBBBBQBQBQBBBBBBBBBBBBBBBBBQBQBBBQBBBBBBBBBBBBBBBBBQBBBBBBBBBQBBBBBrKBBBBBBgJ77rvvJYsLJjSKXSqKPKbqqXdEMRBQBBBBBBBQBBBBBBBBBQBBBBBBBBr .::.ii7vj.
// EBBBBBBBBBBBBBBBBBBBBBBBBBBBBBQBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBQBBBQBQu UBBBBBBbsrrr7LYYsj5XEEEEEEgZggBQBBBBBBBBBBBMSUbQBBBQBBBQBBBBq: ..::ir77J.
// QBBBQBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBQBBBQX.vQBBBBBQMZP22U22PdMQBQBBBBBBBBBBBBBBBQBBI. .iuEBBBBBBMr. .:::.rLL7J:
// :BBBBQBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBQBBBBBBBQBBBBBBBBBBBQBBBBBBB2.iBBBBBBBBBBBBBBBBBBBBBBBBBBBQBBBBBBBBu . ..EBBq: ....:LY77r.
// rBBBBQBBBBBBBBBBBQBQBBBBBBBBBBBBBQBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBr.uBBBBBBQBBBBBBBBBQBBBBBBBBBBBBBBBBM .... .v1 ....rii::
// vQBBBBBBBQBBBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBQBBBQBBBBBBBBBBBBBBBBBBBBBQBr.5BBBBBBBBBBBBBBBQBBBBBBBQBQBBBBBU:..... ..:. ........::::i::..
// vQBQBBBBBBBQBBBBBBBQBBBBBBBQBBBBBBBQBBBQBBBBBBBBBBBQBBBBBBBQBBBBBBBBBQBBBBBBBBBBBBBBBE:iPBBBBBBBBBBBBBBBBBBQBBBBBBBBBBRvi......:rri::.........::i:iir::....
// YQBBBBBBBQBBBBBBBQBQBBBBBBBBBQBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBB::RBBBBBBBBBBBBBBBBBBBQBQBBBBBBRUvii:ri7vviiii:::::::::::iirii::.ii:
// IBBBBBBBBQBBBQBBBBBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBQBBBBBBBBBBBQBBBBBBBBBQBBBBBBBBBBBBBBBQBEr:gBBBBBBBBBBBBBBBBBBQBBBBBBBBBBqr77v77ii:ir7vjJuJjvY7v7777rrii:::i
// UBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBQBBBBBBBQBQBBBBBQBBBQBBBBBBBBq:rQBBBBBQBBBBBQBBBBBBBBBQBBBBBi:rrr7iirL1qKqKq551uJjvsLL7rii::.:BB
// .QBBBBBBBBBBQBBBBBQBBBBBBBBBBBQBQBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBS::QBBBBQBBBBBBBBBBBBBQBBBQBs :rrvvsUEEXLvr7rriiiiii:::....... BBB:
// dBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBQBBBBBQBBBBBBBBBBBBBBBBBBBBBQBBBQBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBXirPBBBQBQBQBBBBBBBBBQBBBBr.irLJ5UuLr::.:.:.:::::.:........ vBBBBv
// 7BBQBBBBBBBBBBBBBQBBBQBBBBBBBBBBBBBBBBBBBQBBBBBBBQBBBBBBBQBBBBBBBBBQBBBBBBBBBBBQBQBBBBBBBBBBBQBBBBBBBBBBBP. 5BBBBBBBBQBBBBBBBBBBBPL2Jiii:::.::::::::::iiiii:::::::.iQB1:rrr.
// BBMgBQBBBBBQBBBBBBBBBQBBBBBBBBBQBBBBBBBBBBBBBBBBBQBQBBBBBBBBBQBQBQBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBQBQBBBBBBg. jBBBBBBBBBBBQBBBBBBBBBv ......:::rrri7rrirrrrrrrr7r7vgBB
// iBBQRBQBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBQBQBBBBBQBBBQBQBBBBBBBQBQBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBD. LBBBBBBBBBBBBBBBBQBBu.:.:.::iiir7ri:........:.::iJRQBd
// qKBQQBBBBBBQBBBQBBBQBBBBBQBBBBBBBQBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBQPXbEMBBBBIqQBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBRgQQQQBQQRQQBQBBBK
//iBBBRQQBBBBBQBBBBBBBBBBBBBQBBBBBBBBBBBBBQBQBBBBBBBQBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBQBBBBBBBQBQBBBQBBBEuvLJ5gBBBQBQBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBQBQ LdBBdL.
//BQRMQQBBBBBQBBBBBBBBBBBQBBBBBBBQBBBBBBBBBQBBBBBBBBBBBBBBBQBBBQBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBZUuLYIRBBQBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBQBBBBBBBQBBBBBBBsUBBBBQBQBBBY
//ZDgQQBBBBBBBBBBBBBBBBBBBBBQBBBBBQBQBBBBBBBBBBBBBBBBBBBBBBBBBQBBBQBBBBBQBBBBBBBBBQBBBBBBBQBQBBBBBBBBBBBBBQBBBBBQBBBPvrvL5DBBBQBBBBBBBBBQBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBQQQBBBQBY
//gEQRBBBQBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBQBQBQBBBBBBBQBBBQBBBBBBBBBQBQBBBBBBBBBBBBBBBBBBBBBBBQBQBBBBBBBQIi:.:YRBBQBBBBBBBBBQBBBBBBBQBBBQBQBQBBBBBQBBBQBBBBBBBQBQQRQMQQQQQRQBBr
//RMQBBBBBBBBBBBQBQBBBQBBBBBBBQBQBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBQBBBQBBBBBBBBBBBBBBBBBBBBBQBBBBBBBQBBBBBBBBBBBQBBBBBuiiirIQBQBBBBBBBBBQBQBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBQBMQRQBBu
//MMBBBBBBBBBBBQBBBBBBBQBBBBBBBBBBBBBBBBBQBQBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBQBQBBBBBBBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBQBBb21vJPBBBBMPBBBQBBBBBBBBBBBBBBBBBBBBBBBQBBBBBBBBBQBQQggggEDDgDRRQBBBv
//RQBBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBQBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBD2j7:i :LZBBBBBBBBBBBBBBBBBBQBBBQBBBBBBBBBBBBBQQRQQQQQMBQBQBQQgQQBBD.
//QBBBBBBQBBBBBQBBBBBQBBBBBBBQBBBBBQBBBQBBBQBQBBBBBBBBBBBBBQBBBBBQBQBBBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBX. igBBBBBBBBBQBBBBBQBBBBBBBQBBBBBBBBBBBBBBBQBBBBBBBQBBBQQgRgRQBBQ.
//BBBBBBBBBBQBBBBBQBBBBBBBBBBBBBQBBBBBBBBBBBBBQBBBBBQBBBQBQBQBBBBBBBBBBBBBBBBBBBQBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBQBQBQBRPPgDRMBBBBBBBBBBBBBBBBBBBBBBBBBBBQBBBBBQBQBQBQBQQMQQQMgDZEDZggggBBB7
(dfs)
#include <bits/stdc++.h>
using namespace std;
int n,num;
int a[250005];
int ans[505][505];
bool b[505][505];
int dx[4] = {0,-1,0,1},dy[4] = {1,0,-1,0};
void dfs(int x,int y){
for(int i = 0; i < 4; i ++){
int nx=x+dx[i],ny=y+dy[i];
if(ans[nx][ny] > ans[x][y]+b[x][y]){
ans[nx][ny] = ans[x][y]+b[x][y];
dfs(nx,ny);
}
}
}
int main() {
cin >> n;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j++){
ans[i][j] = min(min(i,n-i+1),min(j,n-j+1))-1;
b[i][j] = 1;
}
}
for(int i = 1; i <= n*n; i ++){
cin >> a[i];
int x = (a[i]+n-1)/n;
int y = a[i]%n;
if(y == 0) y= n;
num += ans[x][y];
b[x][y] = 0;
dfs(x,y);
}cout << num;
return 0;
}