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
|
|
Solucação em C/C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#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
