Помогите музею
Национальная ассоциация кураторов музеев обратилась к вам с интересной задачей. Президент страны, стремясь улучшить свой общественный имидж, решил посетить различные художественные музеи страны, чтобы создать впечатление утонченного человека. Однако, будучи очень занятым и не зная ничего об искусстве, он установил два ограничения на свои визиты:
В каждом музее он хочет видеть работы только одного художника, чтобы он мог легко подготовиться к визиту и предстать знатоком искусства. Однако ему не обязательно видеть все работы этого художника.
Он не хочет тратить время и требует пройти экспозицию по кратчайшему возможному пути.
Кураторы готовы следовать требованиям Президента, но они не хотят перераспределять шедевры в экспозиции только для того, чтобы получить прямой путь. Их единственная уступка — временно поменять местами два шедевра, если это поможет получить более короткий путь.
Вам нужно написать программу, которая получает на вход план экспозиции и находит кратчайший путь в соответствии с вышеуказанными ограничениями. Чтобы облегчить вашу задачу, кураторы уже определили стандартный план. Рисунок 1 показывает один из таких планов.
Рисунок 1: План музея
Прогулка Президента всегда начинается у левой стены (X = 1, любое Y) и заканчивается у правой стены (X = X_max, любое Y). Прогулка может быть выполнена горизонтально или вертикально; диагональные перемещения не допускаются. Работы данного художника все обозначены одной и той же заглавной буквой (A, B, C и т.д.). Из Рисунка 1 можно проиллюстрировать несколько случаев:
Если президент хочет увидеть работы художника A, пути слева направо нет. Такой путь можно получить, если работу художника B в точке (6, 6) поменять местами с работой художника A из (1, 8), (7, 8), (8, 8), (10, 6), (11, 6) или (11, 3).
Если президент хочет увидеть работы художника B, уже существует путь, начинающийся в (1, 10) и заканчивающийся в (11, 5). Более короткий путь можно получить, если работу D в точке (11, 7) поменять местами с одной из работ художника B, например из (10, 6).
Если президент хочет увидеть работы художника C, уже существует прямой путь от (1, 1) до (1, 11), и более короткий путь получить нельзя.
Если президент хочет увидеть работы D, E или F, возможности получить путь слева направо нет.
Входные данные
Входной файл может содержать несколько экземпляров задачи. Каждый экземпляр имеет следующий формат (все числа — положительные целые):
Первая строка содержит целые числа X_max и Y_max, размеры плана. Можно предположить, что 1 ≤ X_max,Y_max ≤ 100.
Вторая строка содержит букву (заглавную) художника, чьи работы будут посещены.
Y_max строк, каждая с X_max буквами (без пробелов между ними). Первая строка ввода соответствует индексу Y_max, вторая строка — индексу Y_max-1, и так далее, до последней строки, которая соответствует индексу 1.
Строка, содержащая два нуля, завершает входной файл. Числа разделены пробелами.
Выходные данные
Для каждого экземпляра задачи ваша программа должна выводить результат следующим образом.
Если путь существует, ваша программа должна сначала напечатать одну строку с сообщением "Exchange (x,y) and (u,v)", если произойдет обмен, или "No exchange", если обмена не будет. После этого должен быть напечатан кратчайший путь, одна координата на строку. В случае, если существует более одного кратчайшего пути, может быть напечатан любой из них, за исключением того, что путь без обмена должен быть предпочтительнее тех, которые с обменами.
Если путь не существует, ваша программа должна напечатать только одну строку с сообщением "No path".
Вывод каждого экземпляра завершается пустой строкой.