题解 CF677D 【Vanya and Treasure】
小菜鸟
2020-08-13 22:29:58
好题(
我们首先发现此题有明显的分层结构,即按格子内数字分$p$层
然后考虑如何建出分层图来跑最短路。
我们很容易想到两种建图方案:
#### 1.对于每个数字,建出一个$n \times m$的网格图。
此时在每一层内用`bfs`进行多源最短路即可。
最坏情况下$p=n \times m$,要更新约$300\times 300\times 90000$次,`TLE`。
#### 2.对于每个数字,直接将含有该数字的格子作为层内的点。
此时枚举相邻两层之间的全部点对,暴力更新答案即可。
最坏情况下$p=3$,$1$和$2$各占一半,要枚举约$45000\times 45000$对点,`TLE`。
---
我们发现以上两种想法均有其优秀之处,且最坏情况不会同时出现。
那么就可以通过特判使得点对较多(可以$n\times m$为阈值)的两层间用`bfs`更新,较少则枚举点对。
此时最坏情况显然是所有转移全部用`bfs`。点数多的层数不会多,因此最坏情况下更新次数不会超过约$300\times 300 \times 300$次,可以通过此题。
---
以上是在考场上想出解法的心路历程,并无严格证明(因为另一篇题解里的CF老哥已经证明了
但毕竟考场上更看重思想而不是证明(
总而言之就是暴力+特判=正解(不是
放代码
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
typedef std::pair<int,int> point;
int n,m,k,mp[305][305];
std::vector<point> garden[90005];
int dis[305][305],dis2[305][305];
bool vis[305][305];
int dist(point a,point b)
{
return abs(a.first-b.first)+abs(a.second-b.second);
}
void refresh(int lev)
{
for(int i=0;i<garden[lev].size();++i)
{
int ux=garden[lev][i].first,uy=garden[lev][i].second;
for(int j=0;j<garden[lev+1].size();++j)
{
int vx=garden[lev+1][j].first,vy=garden[lev+1][j].second;
dis[vx][vy]=std::min(dis[vx][vy],dis[ux][uy]+dist(garden[lev][i],garden[lev+1][j]));
}
}
}
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
void bfs(int lev)
{
memset(dis2,0x3f,sizeof(dis2));
static std::queue<int> qx,qy;
for(int i=0;i<garden[lev].size();++i)
{
int ux=garden[lev][i].first,uy=garden[lev][i].second;
dis2[ux][uy]=dis[ux][uy];
qx.push(ux);
qy.push(uy);
vis[ux][uy]=1;
}
while(!qx.empty())
{
int ux=qx.front(),uy=qy.front();
qx.pop();qy.pop();
vis[ux][uy]=0;
for(int i=0;i<4;++i)
{
int vx=ux+dx[i],vy=uy+dy[i];
if(vx<0||vx>=n||vy<0||vy>=m)continue;
if(dis2[vx][vy]>dis2[ux][uy]+1)
{
dis2[vx][vy]=dis2[ux][uy]+1;
if(!vis[vx][vy])
{
qx.push(vx);
qy.push(vy);
vis[vx][vy]=1;
}
}
}
}
for(int i=0;i<garden[lev+1].size();++i)
{
int ux=garden[lev+1][i].first,uy=garden[lev+1][i].second;
dis[ux][uy]=dis2[ux][uy];
}
}
void calc()
{
for(int i=0;i<garden[1].size();++i)
{
int ux=garden[1][i].first,uy=garden[1][i].second;
dis[ux][uy]=dist(garden[1][i],point(0,0));
}
for(int lev=1;lev<k;++lev)
{
if(garden[lev].size()*garden[lev+1].size()<n*m)
{
refresh(lev);
}
else
{
bfs(lev);
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
scanf("%d",&mp[i][j]);
garden[mp[i][j]].push_back(point(i,j));
}
}
memset(dis,0x3f,sizeof(dis));
calc();
int res=0x3f3f3f3f;
for(int i=0;i<garden[k].size();++i)
{
int ux=garden[k][i].first,uy=garden[k][i].second;
res=std::min(res,dis[ux][uy]);
}
printf("%d",res);
}
```