- 考虑到答案具单调性(若第 (i) 天能到达目的点,第 (i+1) 天只需向风向相反的方向航行),可以二分答案.
- 现在要考虑给出一个天数 (m) ,问 (m) 天内能否到达目的点.
- 显然,船的航行对 ((x,y)) 的贡献和风对 ((x,y)) 的贡献可以分开计算.
- 由于风向是确定的,且有周期性,预处理出一个周期内影响的前缀和,这部分就可以 (O(1)) 解决.
- 坐标沿风向移动后,判断 (m) 天内能否到达,由于船可以向四个方向走,或者不动,则只需判断曼哈顿距离 (d=|x_1-x_2|+|y_1-y_2|) 是否小于等于 (m).
- 注意二分起始的 (R) 较大,大概设置在 (1e14) 才能得到正确的答案.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define inf 1e14
inline ll read()
{
ll x=0;
bool pos=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
pos=0;
for(;isdigit(ch);ch=getchar())
x=x*10+ch-'0';
return pos?x:-x;
}
ll sx,sy,ex,ey;
const int MAXN=1e5+10;
char s[MAXN];
int sumdx[MAXN],sumdy[MAXN];
int n;
pii calc(char x)
{
if(x=='U')
return mp(0,1);
if(x=='D')
return mp(0,-1);
if(x=='L')
return mp(-1,0);
if(x=='R')
return mp(1,0);
}
bool check(ll m)
{
ll q=m/n,r=m%n;
ll nx=sx+q*sumdx[n]+sumdx[r];
ll ny=sy+q*sumdy[n]+sumdy[r];
ll t=abs(nx-ex)+abs(ny-ey);
if(t>m)
return false;
return true;
}
int main()
{
sx=read(),sy=read();
ex=read(),ey=read();
n=read();
scanf("%s",s+1);
for(int i=1;i<=n;++i)
{
pii dv=calc(s[i]);
sumdx[i]=sumdx[i-1]+dv.first;
sumdy[i]=sumdy[i-1]+dv.second;
}
ll ans=inf;
ll L=0,R=inf;
while(L<=R)
{
ll mid=L+(R-L)/2;
if(check(mid))
R=mid-1,ans=mid;
else
L=mid+1;
}
if(ans==inf)
puts("-1");
else
cout<<ans<<endl;
return 0;
}