Editorial for COCI '12 Contest 5 #2 Arhipelag


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let us create a new matrix representing the (untrimmed) future map of the archipelago. The cells of this matrix are filled in the following way: if the corresponding cell in the input matrix is a sea cell or a land cell surrounded by at least three sea cells, the result is a sea cell; otherwise, it is a land cell.

How can we find cells that surround a given cell? If the current cell has coordinates (r, c), we need to check cells (r, c+1), (r, c-1), (r+1, c), and (r-1, c). It can be done using a for-loop with an index i from 1 to 4, looking at cell (r+u[i], c+v[i]), where the helper arrays u and v are defined as u[] = \{0, 0, 1, -1\}, v[] = \{1, -1, 0, 0\}. However, before indexing a neighbouring cell, we first need to check whether the cell is outside of the matrix boundaries. If it is, we assume that it is a sea cell; otherwise, it is safe to read the cell value.

After determining the future map, we need to find its smallest rectangular part containing all land cells. It can be done by finding the leftmost, rightmost, uppermost, and lowermost land cells, using four variables (min_column, max_column, min_row, max_row), updated as we traverse the future map and reach a land cell. Finally, we simply need to output all rows from min_row to max_row, but only cells from min_column to max_column.


Comments

There are no comments at the moment.