Коник#6917
Ми знаходимося на ярмарку, де нашу увагу привертає атракціон під назвою "Лабіринт Коника", що складається з ряду батутів, пронумерованих невід'ємними цілими числами:
Відвідувачі стрибають з одного батута на інший, прагнучи дістатися до батута в північно-західному куті, де знаходиться вихід з атракціону. Якщо ви дістанетеся до виходу досить швидко, ви можете виграти приз. Однак, щоб претендувати на приз, необхідно дотримуватися наступного правила: після стрибка з батута, позначеного числом , ви повинні приземлитися на інший батут, що знаходиться на відстані батутів у тому ж ряду або стовпці.
Ваше завдання — знайти найкоротший шлях від будь-якого батута до виходу, вимірюваний кількістю стрибків. Оскільки довжина стрибка з кожного батута задана, достатньо позначити кожен батут напрямком оптимального стрибка з нього.
Для заданої початкової позиції шлях вважається коротшим за інший, якщо він вимагає меншої кількості стрибків; у разі рівності перевага надається шляху, перший крок якого веде якомога північніше в масиві; і у разі рівності — якомога західніше.
Замість символів на рисунку ми використовуємо текстові позначення: відповідну сторону світу ('N', 'S', 'E' або 'W') для стрілок, 'X' для батутів без можливого виходу і зірочку '*' для спеціального батута у верхньому лівому куті, який представляє вихід.
Кілька випадків дано в одному тестовому файлі. Перший рядок у кожному тестовому випадку містить пару цілих чисел від до , розділених пробілом; перше число — це кількість рядів, друге — кількість стовпців у матриці. Потім слідують елементи матриці, ряд за рядом, кожен елемент — невід'ємне ціле число, знову розділене пробілами. Матриця 0 \times 0 позначає кінець тестових випадків і, отже, не повинна аналізуватися.
Очікуваний вивід для кожного випадку даних — це матриця символів. Кожен елемент — один із допустимих символів: "N", "S", "E", "W", "X" або "*", як описано вище. Вивід для кожного випадку слідує за порожнім рядком.
Приклад 1