Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Динамическое программирование по подстрокам

Условие задачи  
ID 38134: Сбалансированные подмножества
Сбалансированные подмножества
Темы: Динамическое программирование по подстрокам    Суффиксный массив   

Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек, помеченная упорядоченными парами (i,j) для всех 1≤i≤N, 1≤j≤N (1≤N≤150). Некоторые из этих ячеек содержат траву.
Непустое подмножество ячеек решётки называется "сбалансированным", если выполняются следующие условия:

Все ячейки подмножества содержат траву.
Подмножество 4-связное. Другими словами, существует путь из любой ячейки подмножества в любую другую ячейку подмножества такой, что две последовательные ячейки пути соседствуют горизонтально или вертикально.
Если ячейки (x1,y) (x2,y) (x1≤x2) есть часть подмножества, то все ячейки (x,y) с x1≤x≤x2 также часть подмножества.
Если ячейки (x,y1) and (x,y2) (y1≤y2) есть часть подмножества, то все ячейки (x,y) with y1≤y≤y2 также часть подмножества.
Посчитайте количество сбалансированных подмножеств по модулю 109+7.

Входные данные: 
Первая строка содержит число N.
Каждая их последующих N строк содержит строку из N символов. j-ый символ строки i сверху равен G если ячейка (i,j) содержит траву или символ . в противном случае.

Выходные данные: 
Количество сбалансированных подмножеств по модулю 109+7.
 

Примеры
Входные данные Выходные данные Пояснение
1 2
GG
GG
13 Для этого теста все 4-связные подмножества сбалансированные.

G.  .G  ..  ..  GG  .G  ..  G.  GG  .G  G.  GG  GG
.., .., G., .G, .., .G, GG, G., G., GG, GG, .G, GG
2 4
GGGG
GGGG
GG.G
GGGG
  642
Ниже пример подмножества, которое удовлетворяет второму условию (4-связности), но не удовлетворяет третьему условию:

GG..
.G..
GG..
....