Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2436

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2436

Robô

 

Por OBI - Olimpíada Brasileira de Informática 2013 BR Brazil

Timelimit: 1

Um novo robô de limpeza para um grande salão retangular está sendo desenvolvido. O robô vai percorrer o caminho definido por uma linha marcada no chão, que é coberto com ladrilhos quadrados, brancos e pretos: ladrilhos pretos indicam o caminho que o robô deve percorrer. Ao movimentar-se, o robô pode andar apenas em linha reta, para a frente. Parado, o robô pode girar para as quatro direções (Norte, Sul, Leste e Oeste).

Dados um mapa indicando a cor de cada ladrilho no chão e a posição inicial do robô, você deve escrever um programa que determine a posição final do robô.

 

Entrada

 

A primeira linha contém dois inteiros L e C (1 ≤ L, C ≤ 1000) indicando as dimensões do salão (número de linhas e número de colunas), medidas em ladrilhos. A segunda linha contém dois inteiros A e B (1 ≤ B ≤ L, 1 ≤ BC) indicando respectivamente a linha e a coluna da posição inicial do robô (as linhas são numeradas de 1 a L, de cima para baixo; as colunas são numeradas de 1 a C, da esquerda para a direita). Cada uma das L linhas seguintes contém C inteiros, zeros ou uns. Nessa representação, o valor ‘1’ indica que o ladrilho corresponte é preto. O ladrilho da linha A e coluna B sempre é preto. O caminho do robô é definido unicamente: em nenhum momento o robô necessita fazer uma escolha sobre em qual direção ir (em outras palavras, todo ladrilho preto tem no máximo dois vizinhos pretos e o ladrilho inicial tem um vizinho preto).

 

Saída

 

Seu programa deve imprimir apenas uma linha, contendo dois números inteiros, respectivamente a linha e a coluna da posição final do robô.

 

 

 

Exemplos de Entrada Exemplos de Saída

3 5

1 1

1 0 0 0 1

1 0 0 1 1

1 1 1 1 0

1 5

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>

#define MAXSIZE 1000
char salao[MAXSIZE + 2][MAXSIZE + 2];

int main ()
{

	unsigned short qtsVizinhos;
	unsigned short linha, coluna;
	unsigned short qtsLinhas, qtsColunas;
	unsigned short linhaInicial, colunaInicial;

	scanf("%hu %hu", &qtsLinhas, &qtsColunas);
	scanf("%hu %hu", &linhaInicial, &colunaInicial);

	// Como os índices das linhas e colunas começam em 1
	// rodeio o tabuleiro com 0's, assim tenho certeza que
	// Mesmo que, se alguma hora o laço sair do caminho,
	// O robô não sairá da trilha;
	for (linha = 0; linha  < = qtsLinhas + 1; ++linha)
	{

		salao[linha][0] = 0;
		salao[linha][qtsColunas + 1] = 0;

	}

	for (coluna = 0; coluna  < = qtsColunas + 1; ++coluna)
	{

		salao[0][coluna] = 0;
		salao[coluna + 1][coluna] = 0;

	}

	// preenchimento da matriz;
	for (linha = 1; linha  < = qtsLinhas; ++linha)
		for (coluna = 1; coluna  < = qtsColunas; ++coluna)
			scanf("%hhd", &salao[linha][coluna]);

	qtsVizinhos = 0;
	for (linha = 1; linha  < = qtsLinhas; ++linha)
	{

		for (coluna = 1; coluna  < = qtsColunas; ++coluna)
		{

			// A keyword 'continue' força o laço a executar a próxima iteração
			// Ignorando qualquer código após ela;
			// Se a célula que eu estiver analisando contiver um 0, quer dizer que o Robô
			// Não passará por aqui, por isso posso ignorar;
			 if (salao[linha][coluna] == 0)
				continue;

			// Se não for um 0 na célula, quer dizer que é um 1, as únicas células que têm apenas 1 vizinho
			// são as células de início e de fim, por isso, somo todas as células ao redor e verifico se
			// o resultado é 1;
			qtsVizinhos = salao[linha + 1][coluna] + salao[linha - 1][coluna] + salao[linha][coluna + 1] + salao[linha][coluna - 1];


			if (qtsVizinhos == 1 && (linha != linhaInicial || coluna != colunaInicial))
			{

				printf("%hu %hu\n", linha, coluna);
				return 0;

			}

		}

	}

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3 5
1 1
1 0 0 0 1
1 0 0 1 1
1 1 1 1 0

Output

x
+
cmd
1 5

#2 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#include <queue>
#define MP make_pair
using namespace std;
typedef pair < int, int> ii;
#define MAXN 1010
int visitado[MAXN][MAXN], matriz[MAXN][MAXN], x, y, n, m;
int main() {
    scanf("%d %d %d %d", &n, &m, &x, &y);
    queue < ii> bfs;
    for (int i = 1; i  < = n; i++)
        for (int j = 1; j  < = m; j++) scanf("%d", &matriz[i][j]);
    bfs.push(MP(x, y));
    while (!bfs.empty()) {
        ii davez = bfs.front();
        bfs.pop();
        if (visitado[davez.first][davez.second]) continue;
        x = davez.first;
        y = davez.second;
        visitado[x][y] = 1;
        if (matriz[x + 1][y]) bfs.push(MP(x + 1, y));
        if (matriz[x - 1][y]) bfs.push(MP(x - 1, y));
        if (matriz[x][y + 1]) bfs.push(MP(x, y + 1));
        if (matriz[x][y - 1]) bfs.push(MP(x, y - 1));
    }
    printf("%d %d\n", x, y);
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3 5
1 1
1 0 0 0 1
1 0 0 1 1
1 1 1 1 0

Output

x
+
cmd
1 5
Advertisements

Demonstration


Previous
#2435 Beecrowd Online Judge Solution 2435 Corrida Solution in C, C++, Java, Js and Python
Next
#2437 Beecrowd Online Judge Solution 2437 Distância de Manhattan Solution in C, C++, Java, Js and Python