Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Ibrahim Mesecan.
War Of Battleships
You are the commander of big navy fleet. You are
trying to hit and sink enemy battleships. You will
be given the sea and battleship information on a
square shaped 2D array where ones represent the part of
battleship and zeros represent the sea. Battleship is a
set of adjacent ones in 4 directions. Battleships can
be sunk after m hits where m is the size_of_ship
(number of ones).
Question:
You will be given a 2D matrix and the shots
by the army. Define the number of ships that are sunk.
Input specification
You will be first given two numbers: the size of 2D
array (n) and the number of hits (m) where
1 ≤ n ≤ 100 and 1 ≤ m ≤ 5,000.
Then, the following n lines will have n numbers
(ones or zeros). The following m lines list the shots
(x, y coordinates) by the army.
Output specification:
Show just one integer: the number of ships that are sunk.
Sample Input I
5 6
1 1 0 1 1
1 1 0 0 0
1 1 0 1 0
1 1 0 1 0
0 0 0 0 0
4 1
4 1
2 1
3 1
4 3
4 4
|
Sample Output I
2
|
Explanation:
There are 3 ships given in the matrix. And, the size
of first battleship is 8. So, it can be sunk after 8
hits. The second and the third ships can be sunk after
two shoots. The shots (4,1) hit and sink the second
ship. And the shots (4,3 and 4,4) sink the third ship.
The shot (2,1) hits the first ship, but in order to
sink it 8 hits are required.
Для отправки решений необходимо выполнить вход.
|