UVa 11044 Searching for Nessy （water ver.）

UVa 11044 Searching for Nessy （water ver.）2014-07-14 csdn博客 synapse711044 - Searching for Nessy

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=1985

The Loch Ness Monsteris a mysterious and unidentified animal said to inhabit Loch Ness, a large deep freshwater loch near the city of Inverness in northern Scotland. Nessie is usually categorized as a type of lake monster. http://en.wikipedia.org/wiki/Loch_Ness_Monster

In July 2003, the BBC reported an extensive investigation of Loch Ness by a BBC team, using 600 separate sonar beams, found no trace of any ¨sea monster¨ （i.e., any large animal, known or unknown） in the loch. The BBC team concluded that Nessie does not exist. Now we want to repeat the experiment.

Given a grid of n rows and m columns representing the loch, 6

n, m

10000, find the minimum number s of sonar beams you must put in the square such that we can control every position in the grid, with the following conditions:

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 （she is too big）.

For example,

where X represents a sonar, and the shaded cells are controlled by their sonar beams; the last figure gives us a solution.