UVA 11044 - Searching for Nessy Solution

Problem Statement: Searching for Nessy

Explanation

Some critical point from the problem statement:

• One sonar occupies one position in the grid; the sonar beam controls its own cell and the contiguous cells.
• The border cells do not need to be controlled, because Nessy cannot hide there.

Each sonar occupy a 3 x 3 area and because the border cell do not need to be controlled so we must cover an area of (n-2) x (m-2). Number of sonar needed can be calculated as follow

Num of Sonar = Ceil((m-2)/3) * Ceil((n-2)/3).

Source Code