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á BR 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
1 1 2
2 3 4
8 7 1
1 1
1 2
2 1
2 2
2 3
3 1

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;

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
1 1 2
2 3 4
8 7 1
1 1
1 2
2 1
2 2
2 3
3 1

Output

x
+
cmd
5

#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';
	}
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
1 1 2
2 3 4
8 7 1
1 1
1 2
2 1
2 2
2 3
3 1

Output

x
+
cmd
5

#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();
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
1 1 2
2 3 4
8 7 1
1 1
1 2
2 1
2 2
2 3
3 1

Output

x
+
cmd
5

#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)))
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
1 1 2
2 3 4
8 7 1
1 1
1 2
2 1
2 2
2 3
3 1

Output

x
+
cmd
5
Advertisements

Demonstration


Previous
#1896 Beecrowd Online Judge Solution 1896 It's Time to Duel! Solution in C, C++, Java, Js and Python
Next
#1914 Beecrowd Online Judge Solution 1914 Whose Turn Is It? Solution in C++, Java, Js and Python