题解：P16000 [ICPC 2020 NAC] Hopscotch
aliaosha__s_c1
·
·
题解
思路
首先定义状态：设 f_{i,j} 为按要求走到第 i 行第 j 个格子的最小距离。
对于每个格子 (x,y)，由于只能按照格子上标的数一个个前进，所以可以遍历标的数比它小 1 的另一个格子 (x2,y2)。则可做如下转移：
对于初始化，只需要将每个标有 $1$ 的点 $(x,y)$，做如下处理：
$f_{x,y} \gets 0$。
## 代码
根据推到的状态转移方程，写出代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=55;
const int K=55*55;
int n,k;
int a[N][55],f[55][55];
vector<pair<int,int> >v[K];
int juli(int x1,int y1,int x2,int y2)//返回(x1,y1)到(x2,y2)的距离
{
return abs(x1-x2)+abs(y1-y2);
}
int main()
{
cin>>n>>k;
memset(f,63,sizeof(f));//一开始所有点设置为极大值
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
v[a[i][j]].push_back({i,j});
if(a[i][j]==1)f[i][j]=0;//初始化
}
}
for(int num=2;num<=k;num++)
{
for(int i=0;i<v[num-1].size();i++)
for(int j=0;j<v[num].size();j++)
{
int x1=v[num][j].first,y1=v[num][j].second;
int x2=v[num-1][i].first,y2=v[num-1][i].second;
f[x1][y1]=min(f[x1][y1],f[x2][y2]+juli(x1,y1,x2,y2));
}
}
long long ans=2e9;
for(int i=0;i<v[k].size();i++)
{
int ux=v[k][i].first,uy=v[k][i].second;
if(f[ux][uy]<ans)ans=f[ux][uy];
}
if(ans==2e9||ans==1061109567)return cout<<"-1",0;
return cout<<ans,0;
}
```