Олимпиада
Сейчас идет олимпиада, у меня возникла проблема с задачей про сканворды. Вот условие:
Вася все свое свободное время тратит на решение сканвордов. Сканводр представляет собой прямоугольную таблицу, в пустые клетки которой нужно вписывать слова по горизонтали и по вертикали. В сканводре каждое слово начинается сразу от непустой клеткой или от границы таблицы. Заканчиваются слова соответственно на границе таблицы или перед непустой клеткой. Никакие два слова не следуют друг за другом подряд и не накладываются. Слова могут пересекаться друг с другом только в том случае, если одно слово идет по горизонтали, а второе по вертикали. В сканворде не используются слова длиной меньше двух букв. Для каждого слова в непустые клетки или за границей сканворда записываются вопросы-подсказки, помогающие отгадать слово. Таким образом, любая несвободная клетка может содержать либо вопросы-подсказки, либо рекламу, а во все пустые клетки должны вписываться буквы слов-ответов.
Порешав сотни сканвордов, Вася решил создать свой собственный. Для начала он хочет составить прямоугольную таблицу размером N×M, а затем вписать туда свои слова. При составлении таблицы он случайным образом закрасил часть клеток и решил, что в них будут размещаться вопросы-подсказки. Но тут до него дошло, что при случайном формировании таблицы у него может не получиться правильный сканворд. Так как переделывать всю работу долго, он решил закрасить еще несколько клеток и получить правильный сканворд. Помогите Васе подсчитать, какое минимальное количество клеток придется закрасить.
Формат входных данных:
В первой строке входного файла заданы два целых числа N и M (3 ≤ N, M ≤ 1000). В последующих N строках записано по M символов, причем, символ "." обозначает клетку, в которую будут вписываться буквы, а символ "#" обозначает клетку, в которой будет размещаться вопрос-подсказки или реклама.
Формат выходных данных:
В выходной файл выведите, какое количество клеток нужно закрасить
Пример
input.txt output.txt
3 4
....
....
.... 0
4 3
###
#.#
###
#.# 2
Собственно вопрос - первый пример понятно как решается, все слова верны.
А вот второй пример непонятно - почему ответ 2? Тут имеютися в виду, что слова продолжаются вправо до 2-х симовлов, видимо, но если между точками поставить 1 (один) символ, то тоже получится верный сканворд. Зачем красить направо, если можно красить вниз?
Может кто-нить пояснить логику решения, если не сложно?
Дык у тя точки это не начала слов, а подсказки. 2 подсказки - 2 слова.
В первом примере 16 подсказок и 0 свободных ячеек. Во втором к примеру слово сверху можно разместить и слово снизу. Или еще какие варианты.
Вася хочет составить прямоугольную таблицу размером NxN. Затем он хочет заполнить эту таблицу словами таким образом, чтобы каждое слово было ответом на один из вопросов-подсказок. Вася хочет сделать это так, чтобы все слова были уникальными, а также чтобы никакие два слова не следовали друг за другом и не пересекались. Но у Васи есть одна проблема: он не знает, какие слова нужно использовать.
Помогите Васе придумать слова для его сканворда. Придумайте по одному слову для каждой клетки таблицы, учитывая ограничения, которые Вася установил для своего сканворда.
