You are looking at the floor plan of the Summer Informatics School's new building. You were tasked with SIS logistics, so you really care about travel time between different locations: it is important to know how long it would take to get from the lecture room to the canteen, or from the gym to the server room.
The building consists of n towers, h floors each, where the towers are labeled from 1 to n, the floors are labeled from 1 to h. There is a passage between any two adjacent towers (two towers i and i + 1 for all i: 1 ≤ i ≤ n - 1) on every floor x, where a ≤ x ≤ b. It takes exactly one minute to walk between any two adjacent floors of a tower, as well as between any two adjacent towers, provided that there is a passage on that floor. It is not permitted to leave the building.
The picture illustrates the first example.
You have given k pairs of locations (t__a, f__a), (t__b, f__b): floor f__a of tower t__a and floor f__b of tower t__b. For each pair you need to determine the minimum walking time between these locations.
Input
The first line of the input contains following integers:
Next k lines contain description of the queries. Each description consists of four integers t__a, f__a, t__b, f__b (1 ≤ t__a, t__b ≤ n, 1 ≤ f__a, f__b ≤ h). This corresponds to a query to find the minimum travel time between f__a-th floor of the t__a-th tower and f__b-th floor of the t__b-th tower.
Output
For each query print a single integer: the minimum walking time between the locations in minutes.
Example
Input
3 6 2 3 3
1 2 1 3
1 4 3 4
1 2 2 3
Output
1
4
2
题意:一个人在楼之间穿梭,不同楼层之间通过的楼梯给出范围,穿梭楼层以及不同楼之间的时间为1min,求从目标地到最后的地方需要最少的时间
题解:该题有个大坑-----此人可能在一栋楼上,那么不需要考虑楼层之间的问题;(万幸吃个零食想了出来orz)
那么情况分为两种:
一种是一栋楼,,直接做差即可;
第二种是不同楼,画图可知----走弯路情况只有两种(一个是目的地和出发的都在规定楼层上面,一个是在规定楼层下面),其余情况做差就可
注意:做差时加绝对值
ac代码
#include
#include
#include
using namespace std;
int n,h,low,hig,k;
int main()
{
long long ans;
int ta,fa,tb,fb;
cin>>n>>h>>low>>hig>>k;
for(int i=1; i<=k; i++)
{
cin>>ta>>fa>>tb>>fb;
if(ta==tb)
ans=abs(fa-fb);
else
{
ans=abs(tb-ta);
if(fa
ans+=(fa-hig+fb-hig);
else
ans+=abs(fa-fb);
}
cout<<ans<<endl;
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章