Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2317
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2317
Lobo Mau
Por OBI - Olimpíada Brasileira de Informática 2006 
Brazil
Timelimit: 1
Na fazenda do Sr. Amarante existe um certo número de ovelhas. Enquanto elas estão dormindo profundamente, alguns lobos famintos tentam invadir a fazenda e atacar as ovelhas. Ovelhas normais ficariam indefesas diante de tal ameaça, mas felizmente as ovelhas do Sr. Amarante são praticantes de artes marciais e conseguem defender-se adequadamente.
A fazenda possui um formato retangular e consiste de campos arranjados em linhas e colunas. Cada campo pode conter uma ovelha (representada pela letra ‘k’), um lobo (letra ‘v’), uma cerca (símbolo ‘#’) ou simplesmente estar vazio (símbolo ‘.’). Consideramos que dois campos pertencem a um mesmo pasto se podemos ir de um campo ao outro através de um caminho formado somente com movimentos horizontais ou verticais, sem passar por uma cerca. Na fazenda podem existir campos vazios que não pertencem a nenhum pasto. Um campo vazio não pertence a nenhum pasto se é possível “escapar” da fazenda a partir desse campo (ou seja, caso exista um caminho desse campo até a borda da fazenda).
Durante a noite, as ovelhas conseguem combater os lobos que estão no mesmo pasto, da seguinte forma: se em um determinado pasto houver mais ovelhas do que lobos, as ovelhas sobrevivem e matam todos os lobos naquele pasto. Caso contrário, as ovelhas daquele pasto são comidas pelos lobos, que sobrevivem. Note que caso um pasto possua o mesmo número de lobos e ovelhas, somente os lobos sobreviverão, já que lobos são predadores naturais, ao contrário de ovelhas.
Escreva um programa que, dado um mapa da fazenda do Sr. Amarante indicando a posição das cercas, ovelhas e lobos, determine quantas ovelhas e quantos lobos estarão vivos na manhã seguinte.
Entrada
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém dois inteiros R e C que indicam o número de linhas (3 ≤ R ≤ 250) e de colunas (3 ≤ C ≤ 250) de campos da fazenda. Cada uma das R linhas seguintes contém C caracteres, representando o contéudo do campo localizado naquela linha e coluna (espaço vazio, cerca, ovelha ou lobo).
Saída
Seu programa deve imprimir, na saída padrão, uma única linha, contendo dois inteiros, sendo que o primeiro representa o número de ovelhas e o segundo representa o número de lobos que ainda estão vivos na manhã seguinte.
| Exemplos de Entrada | Exemplos de Saída |
|
6 6 |
0 2 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <set>
#define MAXN 260
#define MAXC 63500
#define MP make_pair
using namespace std;
typedef pair < int, int> ii;
int lobos[MAXC], ovelhas[MAXC], visitado[MAXN][MAXN], componentes, resposta1,
resposta2, n, m;
char matriz[MAXN][MAXN];
void dfs(int x, int y) {
if (x < 0 || y < 0 || x >= n || y >= m || visitado[x][y]) return;
visitado[x][y] = 1;
if (matriz[x][y] == '#')
return;
else if (matriz[x][y] == 'k')
ovelhas[componentes]++;
else if (matriz[x][y] == 'v')
lobos[componentes]++;
dfs(x + 1, y);
dfs(x - 1, y);
dfs(x, y + 1);
dfs(x, y - 1);
}
int main() {
set < ii> cordenadas;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%s", matriz[i]);
for (int j = 0; j < m; j++) {
if (matriz[i][j] == 'k' || matriz[i][j] == 'v')
cordenadas.insert(MP(i, j));
}
}
for (set < ii>::iterator it = cordenadas.begin(); it != cordenadas.end();
it++) {
int coordx = (*it).first, coordy = (*it).second;
if (!visitado[coordx][coordy]) {
componentes++;
dfs(coordx, coordy);
}
}
for (int i = 1; i < = componentes; i++) {
if (lobos[i] >= ovelhas[i]) {
resposta2 += lobos[i];
} else
resposta1 += ovelhas[i];
}
printf("%d %d\n", resposta1, resposta2);
return 0;
}
Input
...#..
.##v#.
#v.#.#
#.k#.#
.###.#
...###
Output