Слово — це максимальний ланцюжок порожніх клітинок -, що йде підряд по горизонталі або по вертикалі, довжиною щонайменше . Отже, треба порахувати такі ланцюжки в обох напрямках.
Найзручніший прийом — розбити кожен рядок за символом #. Отримані шматки і є ланцюжками порожніх клітинок; серед них рахуємо ті, чия довжина не менша за . Просумувавши по всіх рядках, отримаємо кількість слів по горизонталі.
Для вертикалі робимо те саме, але з стовпцями. Найпростіше явно побудувати транспонований кросворд (зібрати кожен стовпець у рядок) і застосувати ту саму процедуру.
Якщо не хочеться будувати транспоновану матрицю, можна пройтися стовпцями напряму, ведучи лічильник довжини поточного ланцюжка: на - збільшуємо його, на # перевіряємо, чи був ланцюжок довшим за одиницю, і обнуляємо. Не забудьте зробити таку ж перевірку в кінці кожного стовпця.
Складність — \mathcal{O}(N^2), тобто до 4 \cdot 10^6 клітинок при N \le 2000. Це прийнятно, але введення варто робити швидким, а транспонування — без зайвих копіювань рядків.