Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2332
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2332
Jogo do Labirinto
Por OBI - Olimpíada Brasileira de Informática 2007 
Brazil
Timelimit: 1
Um amigo seu está muito empolgado com um novo joguinho que baixou em seu celular. O jogo consiste em uma espécie de labirinto que pode ser representado por um quadriculado de células quadradas com N linhas e M colunas. Cada célula do labirinto contém uma plataforma que está a uma determinada altura do chão, que pode ser representada por um inteiro a que varia de 0 (a mais baixa) a 9 (a mais alta). Você inicia na célula (1, 1) (canto superior esquerdo) e o objetivo é chegar na saída do labirinto que fica na célula (N, M) (canto inferior direito).
Para sair do labirinto, você deve fazer movimentos entre células adjacentes. O problema é que seu bonequinho não consegue pular muito alto, então se a célula destino estiver duas ou mais unidades acima da sua altura atual, você não consegue movê-lo. Mais especificamente, a cada turno você pode mover para uma das 4 células adjacentes (cima, baixo, direita, esquerda) caso a altura da célula destino seja menor ou igual à altura da sua célula atual mais uma unidade. Ou seja, se a altura da sua célula for A, você só pode mover a uma célula adjacente caso a altura dela seja menor ou igual a A + 1.
Para complicar um pouco mais o jogo, a cada turno, após o jogador realizar sua ação, cada célula aumenta em uma unidade sua altura, até o valor máximo de 9. Caso a altura de uma determinada célula seja 9, ela passa a ser 0. Note que, em um dado turno, o jogador não é obrigado a se mover, ele pode simplesmente esperar as plataformas subirem ou descerem. Além disso, repare que nem todas as células têm 4 vizinhos, uma vez que não é permitido ao jogador se mover para fora dos limites do labirinto.
Você, como bom programador que é, resolve escrever um programa que calcule a menor quantidade de turnos possível para chegar à saída de um dado labirinto.
Escreva um programa que, dado um labirinto, retorne a menor quantidade de turnos necessária para chegar à saída, de acordo com as restrições dadas.
Entrada
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém dois inteiros N e M (2 ≤ N, M ≤ 50) separados por um espaço em branco, que representam, respectivamente, a quantidade de linhas e colunas do labirinto. As N linhas seguintes contêm, cada uma, M inteiros que representam a altura inicial (no turno 0) da respectiva plataforma. As alturas estão sempre entre 0 e 9 (inclusive).
Saída
Seu programa deve imprimir, na saída padrão, uma única linha, contendo a menor quantidade de turnos possível para sair do labirinto.
| Exemplos de Entrada | Exemplos de Saída |
|
4 3 0 0 0 0 0 0 0 0 0 0 0 0 |
5 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <queue>
#define MP make_pair
#define MAXN 100
using namespace std;
typedef pair < int, int> ii;
typedef pair<int, ii> iii;
int matriz[MAXN][MAXN], processado[MAXN][MAXN];
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i < = n; i++) {
for (int j = 1; j < = m; j++) {
scanf("%d", &matriz[i][j]);
}
}
priority_queue < iii, vector<iii>, greater > bfs;
bfs.push(MP(0, MP(1, 1)));
while (!bfs.empty()) {
iii davez = bfs.top();
bfs.pop();
int x = davez.second.first, y = davez.second.second,
tempo = davez.first;
if (processado[x][y]) continue;
processado[x][y] = 1;
if (x == n && y == m) {
printf("%d\n", tempo);
return 0;
}
if (x + 1 < = n) {
for (int k = 0; k <= 20; k++) {
int a1 = (matriz[x][y] + tempo + k) % 10;
int a2 = (matriz[x + 1][y] + tempo + k) % 10;
if (a1 + 1 >= a2) {
bfs.push(MP(tempo + k + 1, MP(x + 1, y)));
break;
}
}
}
if (y + 1 < = m) {
for (int k = 0; k <= 20; k++) {
int a1 = (matriz[x][y] + tempo + k) % 10;
int a2 = (matriz[x][y + 1] + tempo + k) % 10;
if (a1 + 1 >= a2) {
bfs.push(MP(tempo + k + 1, MP(x, y + 1)));
break;
}
}
}
if (x - 1 >= 1) {
for (int k = 0; k < = 20; k++) {
int a1 = (matriz[x][y] + tempo + k) % 10;
int a2 = (matriz[x - 1][y] + tempo + k) % 10;
if (a1 + 1 >= a2) {
bfs.push(MP(tempo + k + 1, MP(x - 1, y)));
break;
}
}
}
if (y - 1 >= 1) {
for (int k = 0; k < = 20; k++) {
int a1 = (matriz[x][y] + tempo + k) % 10;
int a2 = (matriz[x][y - 1] + tempo + k) % 10;
if (a1 + 1 >= a2) {
bfs.push(MP(tempo + k + 1, MP(x, y - 1)));
break;
}
}
}
}
return 0;
}
Input
0 0 0
0 0 0
0 0 0
0 0 0
Output