Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BATALHA2 - Batalha naval

 

Pedro e Paulo gostam muito de jogar batalha naval; apesar de serem grandes amigos, Pedro desconfia que Paulo não esteja jogando honestamente. Para tirar essa dúvida, Pedro decidiu usar um programa de computador para verificar o resultado do jogo, mas Pedro não sabe programar e por isso pediu a sua ajuda.

O jogo de batalha naval é jogado em um tabuleiro retangular com N linhas e M colunas. Cada posição deste tabuleiro é um quadrado que pode conter água ou uma parte de um navio. Dizemos que dois quadrados são vizinhos se estes possuem um lado em comum. Se duas partes de navio estão em posições vizinhas, então essas duas partes pertencem ao mesmo navio. A regra do jogo proíbe que os quadrados de duas partes de navios distintos tenham um canto em comum (em outras palavras, que quadrados de duas partes de navios distintos compartilhem um vértice).

Cada disparo que um jogador faz deve ser feito em um dos quadrados do tabuleiro do outro jogador. Um jogador informa ao outro a coluna e a linha do quadrado alvo do disparo. Para que um navio seja destruído, o jogador deve acertar todas as partes deste navio. O jogador não pode atirar no mesmo lugar mais de uma vez

Tarefa

Escreva um programa que, dadas a configuração do tabuleiro e uma sequência de disparos feitos por um jogador, determina o número de navios do outro jogador que foram destruídos.

Entrada

A primeira linha da entrada contém números dois inteiros N e M (1 ≤ N ≤ 100 e M ≤ 100) representando respectivamente o número de linhas e de colunas do tabuleiro. As N seguintes linhas correspondem ao tabuleiro do jogo. Cada uma dessas linhas contém M caracteres. Cada caractere indica o conteúdo da posição correspondente no tabuleiro. Se esse caractere for '.', essa posição contém água; se for '#', essa posição contém uma parte de um navio. A próxima linha contém um número K que é o número de disparos feitos pelo jogador (1 ≤ K ≤ N × M). As próximas K linhas indicam os disparos feitos pelo jogador. Cada linha contém dois inteiros L e C, indicando a linha e a coluna do disparo feito pelo outro jogador (1 ≤ L ≤ N e 1 ≤ C ≤ M).

Saída

Seu programa deve imprimir uma única linha contendo um único número inteiro, o número de navios destruído.

Exemplo

Entrada
5 5
..#.#
#....
 ...#.
 #....
 ...#.
5
1 3
1 4
1 5
2 1
3 4

Saída
4

Entrada
5 5
..###
.....
#####
.....
#.##.
5
5 1
5 2
1 3
1 4
1 5

Saída
2

Entrada
7 7
.#....#
###..##
.#....#
....#.#
.#..#.#
.####.#
.......
8
1 1
1 2
2 1
2 2
2 3
3 2
5 2
6 2

Saída
1


Adicionado por:Wanderley Guimarăes
Data:2011-04-28
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2010 - fase 1 nível 2

hide comments
2015-05-24 18:46:43 G
Ele não quer o número de tiros que acertam, ele quer o número de navios destruídos.
2013-12-17 02:17:03 Filipe Portal
Aparentemente apenas entrada/saída estăo de acordo. Se observarmos a segunda entrada e com uma simples contagem podemos verificar que a saída deveria ser 4,năo?
O mesmo acontece para a última, onde a saída deveria ser 7.
Alguém concorda?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.