English version | [ver versão em português]

[PI049] - Lakes and Bulldozers

The Problem

You are given a rectangular map with n rows and m columns that shows land and water. Each cell in the map contains either:

• '#' – land
• '.' – water

A lake is a connected region of water cells ('.') that are adjacent **horizontally or vertically** (not diagonally). Your task is to count how many distinct lakes exist in the initial map.

Then, bulldozers start destroying land. When land is destroyed, it becomes water:

• R x: bulldoze all land cells in row x (i.e., convert all '#' to '.' in that row).
• C x: bulldoze all land cells in column x (convert all '#' to '.' in that column).

After each bulldozing operation, new lakes might form or merge. You must print the number of lakes at each step:

• Before any bulldozing
• After each bulldozer operation

Note: Each row or column is bulldozed at most once.

Example

Initial map (3 rows × 4 columns):

. . . #
. . # .
. # . #

Here, '.' means water and '#' means land. There are 3 lakes: water areas that are not connected to each other.

After bulldozing row 1 (R 1) — all land in that row becomes water:

. . . .
. . # .
. # . #

Now two lakes are connected, and there are 2 lakes.

After bulldozing column 4 (C 4):

. . . .
. . # .
. # . .

Now all water regions are connected, so there is 1 lake.

Input

• First line: integers n and m — number of rows and columns.
• Next n lines: the map of m characters (each either '.' or '#').
• Next line: integer q — number of bulldozing operations.
• Next q lines: each line is either R x (bulldoze row) or C x (bulldoze column).

Output

Print q + 1 lines:

• First, the number of lakes before any bulldozing.
• Then, one line for each bulldozing operation with the updated number of lakes.

Example Input 1

3 4
...#
..#.
.#.#
2
R 1
C 4

Example Output 1

3
2
1

Example Input 2

3 3
###
###
###
3
R 1
R 3
C 1

Example Output2

0
1
2
1

Versão em Português | [see english version]

[PI049] - Lagos e Bulldozers

O Problema

É-lhe dado um mapa retangular com n linhas e m colunas que representa uma paisagem composta por terra e água. Cada célula do mapa contém:

• '#' – terra
• '.' – água

Um lago é uma região conectada de células de água ('.') adjacentes **horizontal ou verticalmente** (não diagonalmente). O seu objetivo é contar quantos lagos distintos existem no mapa inicial.

Depois, bulldozers começam a destruir zonas de terra. Quando a terra é destruída, transforma-se em água:

• R x: destrói todas as células de terra na linha x (ou seja, converte todos os '#' dessa linha em '.').
• C x: destrói todas as células de terra na coluna x (converte todos os '#' dessa coluna em '.').

Após cada operação de bulldozer, novos lagos podem surgir ou lagos existentes podem unir-se. Deve imprimir o número de lagos em cada etapa:

• Antes de qualquer operação de bulldozer
• Após cada operação de bulldozer

Nota: Cada linha ou coluna é destruída no máximo uma vez.

Exemplo

Mapa inicial (3 linhas × 4 colunas):

. . . #
. . # .
. # . #

Aqui, '.' representa água e '#' representa terra. Existem 3 lagos: zonas de água que não estão conectadas entre si.

Após destruir a linha 1 (R 1) — toda a terra dessa linha vira água:

. . . .
. . # .
. # . #

Agora dois lagos ficaram conectados, e há 2 lagos.

Example Input 1

3 4
...#
..#.
.#.#
2
R 1
C 4

Example Output 1

3
2
1

Example Input 2

3 3
###
###
###
3
R 1
R 3
C 1

Example Output2

0
1
2
1

Programação Imperativa (CC1003)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto