HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC16 Group Contests > problem:


34. 50928 - War Of Battleships

IMPC16 Group Contests

Start: Jan.16.2016 at 10:00:00 AM
Finish: Jan.16.2016 at 02:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 15. 50863 - Total Access Cost of a BST
• 21. 50873 - Max Frequency
• 22. 50874 - Apartment Building Adm...
• 23. 50875 - Take m-out
• 24. 50876 - He is my cousin
• 25. 50877 - Friendly Queue
• 32. 50926 - School Mail Merge
• 33. 50927 - Health Expenses
• 34. 50928 - War Of Battleships
• 35. 50929 - Present from your uncles
• F1. 50841 - My grand-grand-grandfa...
• F2. 50936 - Saving the Soldiers
• F4. 50977 - Gaussian Elimination
• F5. 50978 - Albanian Coders
• F6. 50979 - Minimum access cost for...

Feedback

If you notice incorrect translations in Contester, please let author know.

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.



Для отправки решений необходимо выполнить вход.

www.contester.ru