OBI2013, Fase 1, Nível 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 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 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 corresponde é 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: imprimir apenas uma linha, contendo dois números inteiros, respectivamente a linha e a coluna da posição final do robô.
Exemplos
Entrada
3 5 | Saída
1 5 |
Entrada
4 7 | Saída
4 2 |
Solucação em C/C++
#include <stdio.h>
int main(void) {
int mat[1002][1002];
int l,c,a,b, i,j,conta;
scanf("%i %i", &l,&c);
scanf("%i %i", &a,&b);
//preenche com zeros ao redor do chão
for (i=0; i<=l+1; i++) {
mat[i][0]=0;
mat[i][c+1]=0;
}
for (j=0; j<=c+1; j++) {
mat[0][j]=0;
mat[l+1][j]=0;
}
for (i=1; i<=l; i++) {
for (j=1; j<=c; j++) {
scanf("%i",&mat[i][j]);
}
}
while (1) {
mat[a][b]=0;
if (mat[a+1][b]==1) { a=a+1; }
else if (mat[a-1][b]==1) { a=a-1; }
else if (mat[a][b+1]==1) { b=b+1; }
else if (mat[a][b-1]==1) { b=b-1; }
else { break; }
}
printf("%i %i\n", a, b);
return 0;
}
Teste o código: http://ideone.com/Ii9ze7
Teste sua solução: http://olimpiada.ic.unicamp.br/passadas/OBI2013/res_fase1_prog/verifique