【题解】洪水
题目链接
解题思路
本题难度和CSP-S 2020 T1(弱数据)相近
不难得到一个推论:如果你t时刻出发走某一条路径,被某个洪水挡住了,无论你走其他什么路径,总会被挡住。
然后之后又得到一条推论:如果你在t时刻出发去终点,如果某个洪水在半路上挡住了你,那它必然比你更先到达终点。
所以本题就变成了什么时候会有洪水淹没起点,和什么时候会有洪水淹没终点。
代码
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
int mint;
int t[105],x[105],y[105];
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&t[i],&x[i],&y[i]);
}
int a,b,c,d;
for(int i=1;i<=q;i++){
mint=inf;
scanf("%d%d%d%d",&a,&b,&c,&d);
for(int j=1;j<=n;j++){
mint=min(mint,t[j]+abs(x[j]-c)+abs(y[j]-d)-abs(a-c)-abs(b-d));
mint=min(mint,t[j]+abs(x[j]-a)+abs(y[j]-b));
}
printf("%d\n",mint-1);
}
return 0;
}
本文链接:http://kaispace.com.cn/index.php/archives/792/
如果未注明出处,复制公开后需将注明本博客链接。打赏作者