Codeforces Round #180 (Div. 2) B. Sail 【模拟】

B. Sail time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

The polar bears are going fishing. They plan to sail from (sx, sy) to (ex, ey). However, the boat can only sail by wind. At each second, the wind blows in one of these directions: east, south, west or north. Assume the boat is currently at (x, y).

If the wind blows to the east, the boat will move to (x + 1, y). If the wind blows to the south, the boat will move to (x, y - 1). If the wind blows to the west, the boat will move to (x - 1, y). If the wind blows to the north, the boat will move to (x, y + 1).

Alternatively, they can hold the boat by the anchor. In this case, the boat stays at (x, y). Given the wind direction for t seconds, what is the earliest time they sail to (ex, ey)?

Input

The first line contains five integers t, sx, sy, ex, ey (1 ≤ t ≤ 105,  - 109 ≤ sx, sy, ex, ey ≤ 109). The starting location and the ending location will be different.

The second line contains t characters, the i-th character is the wind blowing direction at the i-th second. It will be one of the four possibilities: "E" (east), "S" (south), "W" (west) and "N" (north).

Output

If they can reach (ex, ey) within t seconds, print the earliest time they can achieve it. Otherwise, print "-1" (without quotes).

Examples input 5 0 0 1 1 SESNW output 4 input 10 5 3 3 6 NENSWESNEE output -1 Note

In the first sample, they can stay at seconds 1, 3, and move at seconds 2, 4.

In the second sample, they cannot sail to the destination.

感觉从这道题中吸取的教训很大，做题目该怎么做，拿到题目就着着急急上去做，不想好细节，不看看能不能行得通就直接做是无脑的。以后再也不要犯。这道题就是模拟啊。

#include<iostream> #include<stdio.h> #include<math.h> using namespace std; char a[100010]; long long t,sx,sy,ex,ey; int main() { cin>>t>>sx>>sy>>ex>>ey; getchar(); gets(a); int i,nume=0,numw=0,numn=0,nums=0; for(i=0;a[i];i++) { if(a[i]=='E') nume++; else if(a[i]=='W') numw++; else if(a[i]=='N') numn++; else if(a[i]=='S') nums++; } if(ex-sx>0) { if(nume<ex-sx){ printf("-1\n"); return 0; } } if(ex-sx<0) { if(numw<sx-ex) { printf("-1\n"); return 0; } } if(ey-sy>0) { if(numn<ey-sy) { printf("-1\n"); return 0; } } if(ey-sy<0) { if(nums<sy-ey) { printf("-1\n"); return 0; } } if(ex-sx>=0 && ey-sy>=0) //E N { int pe=ex-sx; int pn=ey-sy; for(i=0;a[i];i++) { if(a[i]=='E' && pe>0) { pe--; } else if(a[i]=='N' && pn>0) { pn--; } if(pe==0 && pn==0) break; } printf("%d\n",i+1); } else if(ex-sx>=0 && ey-sy<=0) //E S { int pe=ex-sx; int ps=sy-ey; for(i=0;a[i];i++) { if(a[i]=='E' && pe>0) { pe--; } else if(a[i]=='S' && ps>0) { ps--; } if(pe==0 && ps==0) break; } printf("%d\n",i+1); } else if(ex-sx<=0 && ey-sy>=0) //W N { int pw=sx-ex; int pn=ey-sy; for(i=0;a[i];i++) { if(a[i]=='W' && pw>0) { pw--; } else if(a[i]=='N' && pn>0) { pn--; } if(pw==0 && pn==0) break; } printf("%d\n",i+1); } else if(ex-sx<=0 && ey-sy<=0) //W S { int pw=sx-ex; int ps=sy-ey; for(i=0;a[i];i++) { if(a[i]=='W' && pw>0) { pw--; } else if(a[i]=='S' && ps>0) { ps--; } if(pw==0 && ps==0) break; } printf("%d\n",i+1); } return 0; } #include <bits/stdc++.h> using namespace std; const int maxn=1e5+5; char a[maxn]; int main() { int n,sx,sy,ex,ey; while(cin>>n>>sx>>sy>>ex>>ey) { cin>>a; bool flag=false; for(int i=0;i<n;i++) { if(a[i]=='N'&&sy<ey) sy++; else if(a[i]=='S'&&sy>ey) sy--; else if(a[i]=='E'&&sx<ex) sx++; else if(a[i]=='W'&&sx>ex) sx--; if(sx==ex&&sy==ey) { flag=true; cout<<i+1<<endl; break; } } if(!flag) cout<<"-1"<<endl; } return 0; }