Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1901
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1901
Butterflies
By Thalyson Nepomuceno, Universidade Estadual do Ceará 
Brazil
Timelimit: 1
The forests of planet called Binox have several rare species of butterflies. Bino is a butterfly hunter and he wants collect the max of different species of butterflies. The forest of Binox is represented by a square grid of size NxN. Each cell of the grid can have one butterfly. The image below represents the first example of input. The species collected were: 1, 2, 3, 4 and 8.
Your task is determine the amount of species of butterflies, which Bino is able to collect, and the only information that you have is the map of the forest and all places visited by Bino. For an unknown reason, Bino always searches in the 2*N positions in the forest.
Input
The input consists of multiples rows. The first row have an integer N (0 < N ≤ 200) representing the size of the forest. The following N rows have N integers Kij (0 < Kij ≤ 1000) each one representing one butterfly specie. The following N*2 rows, each row have 2 integers, representing the cells visited by Bino.
Output
Print out one row with an amount of different species which Bino collected.
| Input Samples | Output Samples |
|
3 |
5 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool procuraEspecie(unsigned *, unsigned numero, unsigned tam);
int main (void)
{
unsigned qtsLinhas, ordem, i;
unsigned linha, coluna;
unsigned qtsEspecies, aux;
while (scanf("%u", &ordem) != EOF)
{
// Declaração de uma matriz onde a quantidade de linhas e colunas
// Tem uma unidade a mais, pois a questão considera a primeira linha e coluna
// Como sendo 1 e não 0 como é o padrão;
unsigned floresta[ordem + 1][ordem + 1];
// Vetor onde irão ficar as espécies já vistas;
unsigned especiesVistas[ordem * ordem];
aux = ordem + 1;
// Inicializa a matriz com todos os valores como 0;
memset(floresta, 0, sizeof(floresta));
// Preenche a matriz;
for (linha = 1; linha < aux; linha++)
for (coluna = 1; coluna < aux; coluna++)
scanf("%u", &floresta[linha][coluna]);
i = 0;
qtsEspecies = 0;
qtsLinhas = ordem * 2;
memset(especiesVistas, 0, sizeof(especiesVistas));
while (qtsLinhas--)
{
scanf("%u %u", &linha, &coluna);
// Se a especie achada ainda não foi vista, a quantidade de espécies
// Capturadas incrementa e a especie atual é colocada no vetor de
// Espécies já vistas;
if (!procuraEspecie(especiesVistas, floresta[linha][coluna], i))
{
qtsEspecies++;
especiesVistas[i++] = floresta[linha][coluna];
}
}
printf("%hu\n", qtsEspecies);
}
}
// Função que procura uma espécie no vetor de espécies;
bool procuraEspecie(unsigned *especiesVistas, unsigned numero, unsigned tam)
{
unsigned i;
for (i = 0; i < tam; i++)
if (especiesVistas[i] == numero)
return true;
return false;
}
Input
1 1 2
2 3 4
8 7 1
1 1
1 2
2 1
2 2
2 3
3 1
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
set < int> s;
int main()
{
int n;
int v[205][205];
int x, y;
while (cin >> n)
{
s.clear();
for (int i = 0 ; i < n ; ++i) for (int j = 0 ; j < n ; ++j)
cin >> v[i][j];
n *= 2;
while (n--)
{
cin >> x >> y;
--x,--y;
s.insert(v[x][y]);
}
cout << s.size() << '\n';
}
}
Input
1 1 2
2 3 4
8 7 1
1 1
1 2
2 1
2 2
2 3
3 1
Output
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.Closeable;
import java.io.Flushable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
static Reader in = new Reader(System.in);
static Writer out = new Writer(System.out);
public static void main(String[] args) throws IOException {
int N = in.nextInt(), b;
Set < Integer> set = new HashSet<>();
int[][] F = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
F[i][j] = in.nextInt();
}
}
for (int i = 0; i < N * 2; i++) {
b = F[in.nextInt() - 1][in.nextInt() - 1];
set.add(b);
}
out.println(set.size());
in.close();
out.flush();
out.close();
}
//////// INPUT / OUTPUT /////////
static class Reader implements Closeable {
private final BufferedReader reader;
private StringTokenizer tokenizer;
public Reader(InputStream input) {
reader = new BufferedReader(
new InputStreamReader(input));
tokenizer = new StringTokenizer("");
}
private StringTokenizer getTokenizer() throws IOException {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
String line = nextLine();
if (line == null) {
return null;
}
tokenizer = new StringTokenizer(line);
}
return tokenizer;
}
public boolean hasNext() throws IOException {
return getTokenizer() != null;
}
public String next() throws IOException {
return hasNext() ? tokenizer.nextToken() : null;
}
public String nextLine() throws IOException {
tokenizer = null;
return reader.readLine();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public float nextFloat() throws IOException {
return Float.parseFloat(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public String[] nextStringArray(int size) throws IOException {
String[] array = new String[size];
for (int i = 0; i < size; i++) {
array[i] = next();
}
return array;
}
public int[] nextIntArray(int size) throws IOException {
int[] array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = nextInt();
}
return array;
}
public long[] nextLongArray(int size) throws IOException {
long[] array = new long[size];
for (int i = 0; i < size; i++) {
array[i] = nextLong();
}
return array;
}
public double[] nextDoubleArray(int size) throws IOException {
double[] array = new double[size];
for (int i = 0; i < size; i++) {
array[i] = nextDouble();
}
return array;
}
@Override
public void close() throws IOException {
tokenizer = null;
reader.close();
}
}
static class Writer implements Closeable, Flushable {
private final PrintWriter writer;
public Writer(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
}
public void println(Object... objects) {
print(objects);
writer.println();
}
@Override
public void close() {
writer.close();
}
@Override
public void flush() {
writer.flush();
}
}
}
Input
1 1 2
2 3 4
8 7 1
1 1
1 2
2 1
2 2
2 3
3 1
Output
#4 Code Example with Python Programming
Code -
Python Programming
n = int(input())
m = []
for g in range(n):
t = [int(x) for x in input().split()]
m.append(t)
v = []
for g in range(2*n):
i, j = [int(x)-1 for x in input().split()]
v.append(m[i][j])
print(len(set(v)))
Input
1 1 2
2 3 4
8 7 1
1 1
1 2
2 1
2 2
2 3
3 1
Output