Problem proposed by: potetisensei

Starting at anywhere on the rink, we can stop on \((1, 1)\), so if the rink is efficient from \((1, 1)\), we can say the rink is efficient from every square. Thus, we just need to consider the case where we start by standing still on \((1, 1)\).

Let us call a row good when we can start at \((1, 1)\) and stop on some of the squares in that row. Similarly, let us call a column good when we can start at \((1, 1)\) and stop on some of the squares in that c.olumn.

The following two conditions are equivalent:

• (A) The rink is efficient from \((1, 1)\).
• (B) All rows are good, or all columns are good.

Let us show this. We will first show that if (B) holds, (A) holds. Assume all rows are good. Choose an arbitrary square \((r, c)\). Since all rows are good, we can stop in the \(r\)-th row. If we then start moving east or west, we can pass \((r, c)\), so (A) holds. The case where all columns are good is similar.

Next, we will show the contraposition of “if (A) holds, (B) holds.” Assume there is \(r\) such that we can stop on none of the squares in the \(r\)-th row, and there is \(c\) such that we can stop on none of the squares in the \(c\)-th column. Thanks to the walls, we can always stop in the \(1\)-st row and in the \(1\)-st column, so neither \(r\) nor \(c\) is \(1\). Here, we can never pass \((r, c)\). This is because, in order to do so, we need to start moving east or west after stopping somewhere in the \(r\)-th row or start moving north or west after stopping somewhere in the \(c\)-th column.

Solution

Thanks to the walls, the following holds:

• The \(1\)-st row is good \(\iff\) The \(1\)-st column is good
• The \(1\)-st row is good \(\iff\) The \(W\)-th column is good
• The \(H\)-th row is good \(\iff\) The \(1\)-st column is good
• The \(H\)-th row is good \(\iff\) The \(W\)-th column is good
• The \(1\)-st row is good

Additionally, if \((r, c)\) is a ground square, the following holds:

• The \(r\)-th row is good \(\iff\) The \(c\)-th column is good

Consider a graph where there is a vertex for each row and each column and there is an edge between each pair of vertices such that “the \(r\)-th row is good \(\iff\) the \(c\)-th column is good.” Changing an ice square to a ground square corresponds to adding an edge to this graph.

The \(r\)-th row is good iff the vertex corresponding to the \(r\)-th row and the vertex corresponding to the \(1\)-st row are connected. That is, all vertices corresponding to the rows are connected iff all rows are good. Thus, the minimum number of changes needed to make all rows good is equal to the minimum number of edges needed to make all vertices corresponding to the rows. We can find this minimum number of edges by subtracting \(1\) from the number of connected components containing vertices corresponding to rows. We can also handle the columns similarly.

Therefore, the answer is \(\min(\text{(the number of connected components containing vertices corresponding to rows)}-1,\) \(\text{(the number of connected components containing vertices corresponding to columns)}-1)\). We can find it by depth-first search or breadth-first search in \(O(HW)\) time, or using disjoint set union.

Sample Implementation in C++

Sample Implementation in Python