printРабочее место участника

printЗадачи

1389. Кирпичи

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

На одной далёкой-далёкой планете внимание исследователей привлёк заброшенный храм. Основное внимание при входе в храм привлекала прямоугольная стена, состоящая `N` колонн по `М` кирпичей в каждой. На каждом кирпиче гордо красовалось выведенное каллиграфическим почерком число. Учёные обнаружили, что прикосновение к кирпичу с числом приводит к его исчезновению. Также исчезает любой кирпич, находящийся рядом с одним из исчезнувших (сверху, снизу, слева или справа), если число на нём отличается от числа на активированном прикосновением кирпиче не более чем на `C`. Процесс продолжается лавинообразно, останавливаясь на кирпичах с числами, отличающимися более чем на `C` от числа на начальном кирпиче. После исчезновения группы кирпичей оставшиеся без опоры кирпичи падают вертикально вниз. В случае исчезновения всех кирпичей одной колонны после вертикального падения происходит сдвиг влево всех колонн, находившихся правее исчезнувшей.
Учёные пришли к выводу, что процесс уничтожения культурной ценности пора прекратить. Но до этого необходимо найти, сколько кирпичей осталось в стене после выполненных исследователями нажатий.
В первой строке входного файла содержатся 3 числа: `N` – количество колонн, `M` – начальное количество кирпичей в каждой колонне (`1 ≤ N, M ≤ 50`) и `C` – разность чисел, поддерживающая волну исчезновений кирпичей (`0 ≤ C ≤ 100`). Далее идут `N` строк по `M` чисел – числа на кирпичах до прикосновений. Вертикальная колонна описана во входных данных горизонтально. Низ колонны соответствует началу строки, верх – концу. Самая левая колонна описана в первой из `N` строк, самая правая в последней.
Затем идёт число `K` – количество прикосновений учёных (`0 ≤ K ≤ 1000`). Далее в `K` строках даны координаты активированных кирпичей `X` – номер колонны слева (`1 ≤ X ≤ N`), затем `Y` – номер ряда снизу (`1 ≤ Y ≤ M`).
Гарантируется, что все нажатия корректны, то есть кирпич с такими координатами во время нажатия существовал.
Выведите в выходной файл одно число – количество кирпичей, оставшихся в стене.

Пример ввода

4 5 1
1 1 3 1 2
3 3 3 3 1
1 5 5 5 1
1 1 4 1 1
3
1 1
1 1
1 1

Пример вывода

7
Источник: XIII Межвузовская олимпиада, г. Вологда, 2010
loading