#include <stdio.h>
#include <stdlib.h>

#define MAX 100

typedef struct { int x; int y; } Item;

#include "fila.c"

void moldura (int a[][MAX], int m, int n) {
  int i, j;
  for (i=0; i<=m+1; i++)
    a[i][0] = a[i][n+1] = -1;
  for (j=1; j<=n; j++) 
    a[0][j] = a[m+1][j] = -1;
}
 
void imprime_caminho (int a[][MAX], int x, int y) {
  printf("(%d,%d) ", x, y);
  while (a[x][y] != 0) {
    if (a[x-1][y] == a[x][y]-1) x--;
    else if (a[x+1][y] == a[x][y]-1) x++;
    else if (a[x][y-1] == a[x][y]-1) y--;
    else if (a[x][y+1] == a[x][y]-1) y++;
    printf("(%d,%d) ", x, y);
  }
  printf("\n");
}

main() {
  int a[MAX][MAX], m, n, i, j, xr, yr; 
  Item atual;

  printf("Digite o tamanho do labirinto: ");
  scanf("%d%d", &m, &n);

  printf("Digite um labirinto com %d linhas e %d colunas:\n", m, n);
  printf("(Digite -1 para parede e -2 para espaço livre.)\n");
  for (i=1; i<=m; i++) 
    for (j=1; j<=n; j++)
      scanf("%d", &a[i][j]);

  moldura(a, m, n);

  printf("Digite a posição inicial do rato: ");
  scanf("%d%d", &xr, &yr);

  printf("Digite a posição do queijo: ");
  scanf("%d%d", &(atual.x), &(atual.y));

  if (a[xr][yr] == -1 || a[atual.x][atual.y] == -1) {
    printf("Nem o rato nem o queijo podem estar em paredes. Entrada inválida.\n"); 
    exit(0);
  }

  a[atual.x][atual.y] = 0;
  cria_fila(m+n);
  insere_fila(atual);
  
  while (!fila_vazia()) {
    atual = remove_fila();
    i = atual.x; j = atual.y;
    if (a[i-1][j] == -2) {
      a[i-1][j] = a[i][j] + 1;
      atual.x = i-1; atual.y = j;
      insere_fila(atual);
    }
    if (a[i+1][j] == -2) {
      a[i+1][j] = a[i][j] + 1;
      atual.x = i+1; atual.y = j;
      insere_fila(atual);
    }
    if (a[i][j-1] == -2) {
      a[i][j-1] = a[i][j] + 1;
      atual.x = i; atual.y = j-1;
      insere_fila(atual);
    }
    if (a[i][j+1] == -2) {
      a[i][j+1] = a[i][j] + 1;
      atual.x = i; atual.y = j+1;
      insere_fila(atual);
    }
  }
  if (a[xr][yr] != -2) 
    /* printf("Há caminho!\n"); */
    imprime_caminho(a, xr, yr); 
  else 
    printf("Não há caminho!\n");
}

/* Teste o funcionamento do programa acima trocando a implementação da
   interface fila.h: troque fila1.c abaixo por fila2.c ou por fila3.c, 
   recompile e veja como o programa funciona igualmente. 

#include "fila1.c"
*/