Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
B. Дарвуулт завь
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Цагаан баавгайнууд загасчилж байна. Тэд ($s_x, s_y$)-ээс ($e_x, e_y$)-рүү аялах гэж байгаа. Тэдний завь зөвхөн салхины хүчээр явдаг. Секунт бүрд салхи урд, хойд, баруун, зүүн зүгрүү салхилдаг. Завь нь ($x, y$) байгаа гэж үзвэл
- Хэрвээ салхи зүүн зүгт салхилвал завь ($x+1, y$)-рүү шилжинэ
- Хэрвээ салхи урд зүгт салхилвал завь ($x, y-1$)-рүү шилжинэ
- Хэрвээ салхи баруун зүгт салхилвал завь ($x-1, y$)-рүү шилжинэ
- Хэрвээ салхи хойд зүгт салхилвал завь ($x$, $y+1$)-рүү шилжинэ
Мөн тэд завиа зангуугаар зогсоож болдог. Энэ тохиолдолд завь ($x, y$) координат дээрээ үлдэнэ. Өгөгдсөн салхи $t$ секунт үргэлжлэх үеийн чиглэл өгөгдсөн бол ($e_x, e_y$)-т очиход зарцуулах хамгийн бага хугацааг ол.
Оролт
Эхний мөр $t$, $s_x$, $s_y$, $e_x$, $e_y$ ($1 ≤ t ≤10^5$, $-10^9 ≤ s_x, s_y, e_x, e_y ≤ 10^9$) тоонууд өгөгдөнө. Эхлэх байрлал нь төгсөх байрлалаас ялгаатай байна.
Хоёрдох мөр нь $t$ тэмдэгт агуулна. $i$ дах тэмдэгт нь салхины $i$ дахь секунд дахь чиглэлийг заана. Энэ нь дараах 4 боломжтой : E (зүүн) S (урд) W (баруун) N (хойд).
Гаралт
Хэрвээ тэд ($e_x, e_y$)-д $t$ секундэд очсон байж чадах бол очиход зарцуулах хамгийн бага цагийг чадахгүй бол "-1"-г хэвлэ.
Орчуулсан: Баттулга
Жишээ тэстүүд
Оролт
5 0 0 1 1 SESNW
Гаралт
4
Оролт
10 5 3 3 6 NENSWESNEE
Гаралт
-1
Тэмдэглэл
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.