Дивна Стрілянська Подорож
Європейська юніорська олімпіада з інформатики 2542 року відбувається в Стрільяндії. Стрільяндія має форму таблиці з m рядків (пронумерованих від 0 до m - 1) і n стовпців (пронумерованих від 0 до n - 1), в кожній клітинці якої розташоване місто. Позначимо клітинку в рядку r і стовпці c як (r, c). Гуртожиток, де проживають учасники, знаходиться в клітинці (0, 0), а зал змагань — у клітинці (m - 1, n - 1).
Особливістю Стрільяндії є те, що в деяких містах встановлені величезні стрілки. За одну операцію стрілку можна повернути на 90 градусів за годинниковою стрілкою. Спочатку кожна стрілка вказує на північ, схід, південь або захід. Організатори олімпіади хочуть скористатися цією особливістю для навігації учасників.
Учасники слідуватимуть за стрілками, переходячи з кожного міста в сусіднє за напрямком стрілки. Якщо вони потраплять у місто без стрілки або вийдуть за межі Стрільяндії, вони заблукають і не зможуть взяти участь в олімпіаді. Організатори прагнуть, щоб усі учасники безпечно дісталися до залу змагань з гуртожитку (клітинка (0, 0)) до залу змагань (клітинка (m - 1, n - 1)). Для цього вони можуть повернути деякі стрілки. Допоможіть їм визначити мінімальну кількість поворотів стрілок, необхідну для досягнення мети, або повідомте, що учасники не зможуть дістатися до залу змагань за будь-якої орієнтації стрілок.
Вхідні дані
Перша рядок містить два цілі числа m і n (1 ≤ n, m ≤ 500) — кількість рядків і стовпців. Наступні m рядків містять по n символів, що задають початковий напрямок стрілок (N — північ, E — схід, S — південь, W — захід, X — немає стрілки). Останній символ останнього рядка (тобто символ, що відповідає залу змагань) завжди буде X. Символ N означає напрямок "вгору", E означає "вправо", S означає "вниз", і W означає "вліво". Кожна клітинка містить один з символів: N, E, S, W, X.
Вихідні дані
Виведіть мінімальну кількість поворотів стрілок, які потрібно зробити організаторам. Якщо рішення не існує, виведіть -1.
Пояснення до першого прикладу
Оптимальне рішення — змінити W в клітинці (1, 2) на S, повернувши стрілку три рази.
Пояснення до другого прикладу
Тут нічого робити не потрібно, учасники і так дістануться до залу змагань.
Пояснення до третього прикладу
Повернути стрілку в клітинці (0, 0) один раз (щоб отримати S), стрілку в клітинці (1, 0) два рази (щоб отримати E), і стрілку в клітинці (2, 1) один раз (щоб отримати E).