AT_abc413_f 题解
也许是 ABC413 最难的一道？但我感觉也挺水的。
题目就是说，你在玩一个游戏，这个游戏中有一个网格，上面有若干个洞，然后网格上还有一枚棋子，你可以移动这个棋子走上下左右四个方向。你希望这枚棋子尽早掉进洞里，但系统希望棋子不要掉进洞里，因此每次你要移动棋子的时候，系统都会明智选择出一个方向，拦住你。也就是说，每次移动，你都只有三个方向可以选择。假若你和系统都坚守各自的目标，选择最优方案，请问你的棋子需要走多少步才会掉进洞里，如果永远不会掉进洞里那么算作
理解了题目就会发现，这很像一个次短路。
难道不是吗？系统肯定是会拦截你能够最快到达洞里的那个方向对吧，但你可以走次短路啊。次短路虽然不是最优，但它也是榜二老大了，没错吧。
但是肯定无法从每个点出发各跑一次啊，那时间复杂度肯定炸了。
对啊对啊，正着不行那就反着来嘛。我们先把所有洞的坐标压进去，然后再反过来跑就完事儿哩。
不知道标准次短路该怎么写，我也没学过次短路，但思考一下吧，第一次到达这个点是最短路，第二次不就是次短路了嘛。所以跑常规 BFS 就行，但这里不是直接用标记数组，而是统计到达次数。第一次来咱们不管，第二次到达再处理。
然后本题就结束了，并不难，对吧。
最后上代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 3005;
const long long Inf = 0x3f3f3f3f3f3f3f3f;
queue<pair<int,int>> q;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
long long n,m,k,dis[N][N],c[N][N],ans;
int main(){
cin>>n>>m>>k;
memset(dis,0x3f,sizeof(dis));
while(k--){int x,y;cin>>x>>y;dis[x][y]=0,q.push({x,y});}
while(!q.empty()){
auto [x,y]=q.front();q.pop();
for(int o=0;o<4;o++){
int x2=x+dx[o],y2=y+dy[o];
if(x2<1||x2>n||y2<1||y2>m)continue;
if(dis[x2][y2]!=Inf)continue;
if((++c[x2][y2])!=2)continue;
dis[x2][y2]=dis[x][y]+1,q.push({x2,y2});
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)ans+=(dis[i][j]==Inf?0:dis[i][j]);
cout<<ans<<"\n";
return 0;
}