Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2371
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2371
Naval Battle
OBI - Olimpíada Brasileira de Informática 2010 
Brazil
Timelimit: 1
Pedro and Paulo love to play Naval Battle; despite being good friends, Pedro suspects that Paulo is not playing honestly. To fix this, Pedro decided to use a computer program to verify the game result, but he doesn't know how to program so he asked for your help. The naval battle it's a board game with N lines and M columns. Each position in this board is a square that can contain water or a ship piece. Two squares are neighbors if they have a side in common. If both ship parts are on neighbors then these pieces belong to the same ship. One rule forbids that two different ships share a single ship part (in other words, the squares of two different ship parts are in the same position). Each shot that one player does must be thrown at the board of the other player. The other player tells the other the line and column where he wants to shoot. To destroy a ship, the player must hit all its ship pieces. A player mustn't shoot in the same place twice.
Write a program that, given the information about the board and the shots given by the player, determines the number of ships that were destroyed.
Input
The first input line contains two integers N and M (1 ≤ N ≤ 100 e M ≤ 100), representing respectively the number of lines and columns of the board. The next N lines correspond to the board game. Each of these lines contain M characters. Each character indicates the content of the position of the board. If this character is '.', then this position contains water; if it's '#', this position contains a ship piece. The next line contains a number K with the number of the shots given by the player (1 ≤ K ≤ N × M). The next K lines contain two integers L and C, indicating the the line and column of the shot made by the other player (1 ≤ L ≤ N e 1 ≤ C ≤ M).
Output
Your program must print a single line containing an integer, the number of the ships destroyed. Be careful that when one group of test cases that totalizes 30 points, the ships are composed by one piece (or a square position) and if it totalizes 50 points, each ship is contained exactly within one line.
| Input Samples | Output Samples |
|
5 5 |
4 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <map>
#include <set>
#include <vector>
#define MAXN 10010
#define MAXL 110
using namespace std;
vector<int> lista[MAXN];
map < pair<int, int>, int> mapa;
map<pair<int, int>, int>::iterator it;
map < int, int> navios;
map<int, int>::iterator jt;
int componente[MAXN], k, n, m, resposta, contador;
char entrada[MAXN];
void dfs(int z) {
for (int i = 0; i < lista[z].size(); i++) {
int v = lista[z][i];
if (componente[v] == -1) {
componente[v] = componente[z];
dfs(v);
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i < = n; i++) {
scanf("%s", entrada);
for (int j = 0; j < m; j++) {
if (entrada[j] == '#') {
contador++;
componente[contador] = -1;
mapa[make_pair(i, j + 1)] = contador;
}
}
}
for (it = mapa.begin(); it != mapa.end(); it++) {
int x = (*it).first.first, y = (*it).first.second, id = (*it).second;
pair < int, int> a1 = make_pair(x + 1, y), a2 = make_pair(x - 1, y),
b1 = make_pair(x, y + 1), b2 = make_pair(x, y - 1);
if (mapa.find(a1) != mapa.end()) lista[id].push_back(mapa[a1]);
if (mapa.find(a2) != mapa.end()) lista[id].push_back(mapa[a2]);
if (mapa.find(b1) != mapa.end()) lista[id].push_back(mapa[b1]);
if (mapa.find(b2) != mapa.end()) lista[id].push_back(mapa[b2]);
}
for (int i = 1; i < = contador; i++) {
if (componente[i] == -1) {
resposta++;
componente[i] = resposta;
dfs(i);
}
}
for (int i = 1; i < = contador; i++) {
if (navios.find(componente[i]) != navios.end())
navios[componente[i]]++;
else
navios[componente[i]] = 1;
}
scanf("%d", &k);
for (int i = 0; i < k; i++) {
int a, b;
scanf("%d %d", &a, &b);
pair < int, int> par = make_pair(a, b);
if (mapa.find(par) != mapa.end()) navios[componente[mapa[par]]]--;
}
for (jt = navios.begin(); jt != navios.end(); jt++) {
if ((*jt).second != 0) resposta--;
}
printf("%d\n", resposta);
return 0;
}
Input
..#.#
#....
...#.
#....
...#.
5
1 3
1 4
1 5
2 1
3 4
Output