/**************
para compilar 
gcc -pedantic-errors -Wall -std=c99 labirinto.c -o labirinto
para executar
./labirinto < pequeno.txt
**************/

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

//funcoes auxiliares
void print_position(int x, int y);
void print_maze(char **maze, int largura, int altura);

//devolver 1 se chego na saida a partir de maze[x_atual][y_atual]
// 0 caso contrario
int labirinto(int x_atual, int y_atual, char **maze, int largura, int altura){
  if(x_atual < 0 || x_atual >= largura || y_atual < 0 || y_atual >= altura)
    return 0;
  if(maze[x_atual][y_atual] == 'S')
    return 1;
  if(maze[x_atual][y_atual] == 'X' || maze[x_atual][y_atual] == '#')
    return 0;
  
  char temp = maze[x_atual][y_atual];
  maze[x_atual][y_atual] = '#';
  if(labirinto(x_atual, y_atual + 1, maze, largura, altura) == 1) return 1;
  if(labirinto(x_atual - 1, y_atual, maze, largura, altura) == 1) return 1;
  if(labirinto(x_atual, y_atual - 1, maze, largura, altura) == 1) return 1;
  if(labirinto(x_atual + 1, y_atual, maze, largura, altura) == 1) return 1;
  maze[x_atual][y_atual] = temp;
  return 0;
}

//voce nao precisa mexer no main
int main(void){
  int largura, altura, x_entrada, y_entrada, x, y;
  
  scanf("%d %d\n", &largura, &altura);

  char ** a = malloc(largura * sizeof(char*));
  for(x = 0; x < largura; x++){
    a[x] = malloc(altura * sizeof(char));
  }
   
  for(y = altura - 1; y >= 0; y--){
    for(x = 0; x < largura; x++){
      a[x][y] = getchar();
      if(a[x][y] == 'E'){
        x_entrada = x; 
        y_entrada = y;
      }
    }
    getchar(); //pegar a quebra de linha
  }

  
  print_maze(a, largura, altura);
  printf("\n");

  //eu acredito que seja mais facil comecar a busca pela saida
  labirinto(x_entrada, y_entrada, a, largura, altura); 
  
  print_maze(a, largura, altura);

  printf("\n");

  return 0;
}


//voce nao precisa mexer nas funcoes auxiliares
void print_maze(char **maze, int largura, int altura){
  int x, y;
  for(y = altura - 1; y >= 0; y--){
    for(x = 0; x < largura; x++){
      printf("%c", maze[x][y]);
    }
    printf("\n");
  }
}

void print_position(int x, int y){
  printf("(%d, %d)", x, y);
}