Задача №113520. Лабиринт
Уолеви разработал игру, в которой игрок собирает монеты в лабиринте. На данный момент проблема в том, что игра слишком проста. Могли бы вы создать несколько сложных лабиринтов для игры? Каждый лабиринт представляет собой прямоугольную сетку, состоящую из полов (.) И стен (#). Одна из ячеек является базой (x), а некоторые ячейки могут содержать монеты (0). Игрок начинает в базе и может перемещаться влево, вправо, вверх и вниз. Задача игрока - собрать все монеты в лабиринте, а затем вернуться на базу. Трудность лабиринта - это длина кратчайшего пути, который начинается на базе, собирает все монеты и возвращается на базу.
Ввод начинается с целого числа t: количество лабиринтов. После этого следуют t строк. Каждая такая строка содержит три целых числа n, m и k. Это означает, что размер лабиринта должен быть n * m ячеeк, и должно быть ровно k монет.
Выход должен содержать описания лабиринта, разделенные пустыми строками, в том же порядке, что и на входе. Каждый лабиринт должен быть разрешен.
2 3 3 1 4 7 2
### #.x #o# .o.#### .#..x.# ...##.# ###o...
Трудность первого лабиринта - 4, а трудность второго лабиринта - 18.
Это задача только для вывода, и есть только один входной файл . Вы можете скачать входной файл здесь. Вы должны представить выходной файл, содержащий все лабиринты, указанные во входном файле.
Для каждого лабиринта ваш счет max(0, 100 - 3(d - x)) - где x трудность вашего лабиринта и d сложность самого сложного лабиринта, найденного жюри. Ваш общий балл для задания - это среднее значение всех оценок, округленное до целого.