Solução Informática - Nível Iniciante - Semana 7

Solução por Anita Ramos

Problemas como este são muito comuns em provas de olimpíada, como a $OBI$ , no nível iniciante em que temos que trabalhar com uma matriz e analisar os vizinhos de um determinado ponto. Por isso, é essencial o compreendimento de toda a solução a seguir.

Iniciando a programação então, após adicionar a biblioteca e declarar as variáveis, o programa lê os primeiros valores de entrada $L$ , $C$ , $A$ e $B$ e usamos dois loops com o comando $for()$ para ir de ponto em ponto no eixo X e no eixo Y e ler o valor desse ponto, por exemplo, no exemplo de entrada 1, temos que o valor de $v[2][4]$ é 1, enquanto que os valores de $v[2][3]$ e $v[1][4]$ são 0. Depois, temos as variáveis $lasta$ e $lastb$ , que inicialmente são as coordenadas do ponto inicial, ou seja, $A$ e $B$ , que irão guardar o $x$ e o $y$ do ponto que iremos analisar.

Na parte da lógica do programa, temos um loop com o comando $while()$ para checar todos os pontos da matriz. Dentro dele, vamos checar todos os vizinhos desse ponto a partir da seguinte ideia: pela coordenada do ponto principal, determinamos as coordenadas dos seus vizinhos (com auxílio dos valores de $vA$ e de $vB$ ). Se esse vizinho for o vizinho anterior, ou seja, o que deu origem a esse ponto que estamos analisando, não podemos o considerar (por isso, $d=1$ ), já que estaríamos percorrendo o trajeto do robô ao contrário. Depois, se esse vizinho não for o vizinho anterior ( $d=0$ ) e seu valor for 1, então salvamos as coordenadas desse novo ponto e salvamos também as coordenadas do ponto que deu origem a esse novo, ou seja, do ponto que ainda estamos analisando. Por fim, encerramos esse loop de checar os vizinhos (então $k=5$ ) para seguir para o próximo ponto do caminho do robô e somamos 1 a variável $cont$ para contabilizar que mais um ponto da matriz foi checado.

No final, apenas imprimimos as coordenadas do ponto final do robô e o programa retorna 0.

Segue o código comentado para melhor compreensão da solução:

	#include<bits/stdc++.h> //biblioteca utilizada
	using namespace std;
	const int MAXN=1100; //define o valor de MAXN
	int v[MAXN][MAXN]; //declara uma matriz com tamanho MAXN x MAXN
	int vA[4]={1,0,-1,0}; //declara um vetor 'vA' já com valores na memória
	int vB[4]={0,1,0,-1}; //declara um vetor 'vA' já com valores na memória
	int main()
	{
	int L,C,i,j,A,B,lasta=0,lastb=0,cont=0,a,b,k,d=0,la,lb; //declaração de variáveis
	scanf("%d %d", &L, &C); //lê a primeira linha de entrada, ou seja, 'L' e 'C'
	scanf("%d %d", &A, &B); //lê a segunda linha de entrada, ou seja, 'A' e 'B'
	for(i=1; i<=L; i++) //parte 1 do loop para ler todos os números da matriz (nesse caso, ele vai linha por linha)
	{
	for(j=1; j<=C; j++) //parte 2 do loop para ler todos os números da matriz (nesse caso, ele vai coluna por coluna)
	{
	scanf("%d", &v[i][j]); //lê o valor (0 ou 1) de uma posição na matriz
	}
	}
	lasta=A; //'lasta' assume o valor de 'A'
	lastb=B; //'lastb' assume o valor de 'B'
	while(cont<=L*C) //enquanto não checar todos os pontos de uma matriz
	{
	for(k=0; k<4; k++) //loop para checar os 4 vizinhos
	{
	d=0; //'d' é zerado
	a=lasta+vA[k]; //'a' assume o valor do 'eixo x' de um vizinho
	b=lastb+vB[k]; //'b' assume o valor do 'eixo y' de um vizinho
	if(a==la && b==lb) //se o vizinho for o vizinho anterior, ou seja, o vizinho que deu origem a esse novo ponto
	{
	d=1; //'d' assume o valor de 1 para não considerarmos esse vizinho
	}
	if(v[a][b]==1 && d!=1) //se o vizinho tem valor 1 e não é o vizinho anterior
	{
	la=lasta; //'la' assume o valor de 'lasta'
	lb=lastb; //'lb' assume o valor de 'lastb'
	lasta=a; //'lasta' assume o valor de 'a'
	lastb=b; //'lastb' assume o valor de 'b'
	k=5; //'k' assume o valor de 5 para encerrar esse loop
	}
	}
	cont++; //soma-se 1 a variável cont
	}
	printf("%d %d", lasta, lastb); //imprimi 'lasta' e 'lastb', ou seja, os pontos das coordenadas x e y, respectivamente da posição final do robô
	return 0; //retorna a 0
	}

view raw

Robô.cpp

hosted with ❤ by GitHub