题解 CF677D 【Vanya and Treasure】

小菜鸟

2020-08-13 22:29:58

Solution

好题( 我们首先发现此题有明显的分层结构,即按格子内数字分$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); } ```