Comments 11
Г-образный морской бой:
Бежим по полю ищем звёздочку. Если встречаем, заменяем ее на что-то другое (на x) чтобы не зациклилось, рекурсивно проверяем и заменяем соседние, ищем минимальную и максимальную координаты. Получаем левый верхний и правый нижний угол поля, содержащего корабль. Анализируем, можно сравнить с шаблонами, можно аналитически - это квадрат, кол-во символов корабля (1,3,5,7) и их взаимную симметрию.
Пардон, я не привыкший решать задачки, но с Морским боем у меня непонятки уже на этапе условий задачи (какое-то "это" поле например), я конечно почитал решение и понял о чем там речь, но написать нужно было так:
Дано поле M*N с уже размещенными кораблями, где символом "точка" отмечаются пустые ячейки, а символом "звезда" элементы корабля. Нужно проверить - являются ли все расставленные корабли соответствующими набору "Г"-образных кораблей и соблюдаются ли условия взаимного размещения - на соседних ячейках разных кораблей не должно быть ячеек "звезда" ни по горизонтали, ни по вертикали, ни по диагонали.
Так же в условии ничего не сказано про границу поля. Видимо граница может соприкасаться с кораблём. Но в примерах кораблей и затем в шаблонах явно указана невозможность соприкасания с границей поля.
Касательно решения - так как шаблоны друг от друга отличаются, но и подобранный шаблон будет блокировать часть поля как одобренную (ну или прерываться если будет нарушено хотя бы одно условие). Отсюда потребуется хранить информацию о всё еще непроверенных ячейках.
Я бы предложил такое решение:
Делаем проход по M*N и проверяем на такие основные признаки:
а) ищем корабли 1х1
...
.*.
...б) ищем шаблоны для возможных частей кораблей
.*. ... ... .*.
.** .** **. **.
... .*. .*. ...Сохраняем информацию и найденных шаблонах в виде координат центральной точки. Дальнейшие проверки делаем отталкиваясь от них.
Я с шаблонами работал ранее и мне понравилась линейная схема хранения шаблонов, например шаблон
...
.*.
...хранится как
{{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {0, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}}Тут за опорную точку взят центральный сектор, это если привязываться к тому, что я описал выше, в целом можно привязаться к любой точке, но именно здесь удобно это делать на сектор, который есть во всех шаблонах и является центром вращения.
В задаче «Подсистема регистрации» регулярное выражение опубликовали частично. И в итоге оно работает не правильно. Проверьте пожалуйста. Именно в этом месте имеет значение каждый символ.
Считаем, сколько заплатить в магазине и проверяем поле морского боя: разбор задач для разработчиков C#, iOS и Android