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

char buffer[110][110][1000];
int  len[1000];
char maze[110][110];
char bestmaze[110][110];
int  bufcount=0, stopx, stopy;
int steps=0;
int startx, starty, beststep=99999, bestindex, width, height;
char hei[100];

int wmap[110][110];


void print_maze(FILE *f) {
  int x, y;

  for (y=0; y<height; ++y) {
    for (x=0; x<width; ++x) {
      if ((x == startx) && (y == starty))
	fprintf(f, "*");
      else if((x == stopx) && (y == stopy))
	fprintf(f, "$");
      else
	fprintf(f, "%c", maze[y][x]);
    }
    fprintf(f, "\n");
  }
}

void traverse(int x, int y)
{
  if (wmap[y][x] < steps)
    return; 

  wmap[y][x] = steps;

  if (steps > beststep)
    return;

//  if (maze[y][x] == 'x')
//    return;

//  if (maze[y][x] == '.')
//    return;

  if (maze[y][x] == '$') {
    if (beststep > steps) {
      beststep = steps;
      memcpy(bestmaze,maze,110*110);
    }
    return;
  }

  if ((maze[y][x] == ' ') || ((maze[y][x] == '*') && (steps == 0))) {
    steps++;
    maze[y][x] = '.';
    if ((maze[y][x+1] == ' ') || (maze[y][x+1] == '$')) traverse(x+1,y);
    if ((maze[y+1][x] == ' ') || (maze[y+1][x] == '$')) traverse(x,y+1);
    if ((maze[y][x-1] == ' ') || (maze[y][x-1] == '$')) traverse(x-1,y);
    if ((maze[y-1][x] == ' ') || (maze[y-1][x] == '$')) traverse(x,y-1);
    maze[y][x] = ' ';
    steps--;
  }
}


int main(int argc, char **argv) {

  FILE *fp, *fp2;
  char temp[] = "maze.in";
  int i, count, j;
  int x, y;
  char _temp[110];
  
  printf("kjører...\n");

  if (!(fp = fopen(temp, "r"))) {
    printf("kan ikke åpne inputfil.\n");
    return 1; 
  }

  fp2 = fopen("maze.out","w");
  
  fgets(_temp, 110, fp);
  sscanf(_temp, "%i", &count);

  memset(len, 0x00, sizeof(len));

  for (i=0; i<count; ++i) {
    beststep=99999;
    for (y=0; y<110; ++y)
      for (x=0; x<110; ++x)
	wmap[y][x] = 99999;
    steps=0;
    fgets(_temp, 110, fp);
    
    sscanf(_temp, "%i %i", &width, &height);
    for (j=0; j<height; ++j)
      fgets(maze[j], 110, fp);

    for (y=0; y<height; ++y)
      for (x=0; x<width; ++x) {
	if (maze[y][x] == '$') {
	  stopx = x;
	  stopy = y;
	}
	if (maze[y][x] == '*') {
	  startx = x;
	  starty = y;
	}
      } 
    traverse(startx, starty);
    if (beststep == 99999) {
      print_maze(fp2);
      fprintf(fp2,"This maze has no solutions.\n");
    } else {
      memcpy(maze,bestmaze,110*110);
      print_maze(fp2);
      fprintf(fp2,"The optimal path is %i steps.\n", beststep);
    }
  }



  printf("ok.\n");
  return 0;
}