//
//  Maze.java
//  MazeTest
//
//  Created by Gerhard Dueck on 11-02-08.
//  Modfied by David Bremner 2018-02-18
//
import java.io.*;
import java.util.*;
enum Cell {
    WALL, FOUND, EXPLORED, PATH, START, FINISH  }

public class Maze {

    private Cell[][] map;
    int n,m; // n x m map

    private int startr, startc, targetr, targetc;

    private static char[] symbols = {'*', 'p', '-', ' ', 'S', 'F'};

    public void readMap(String fileName){
        try {
            BufferedReader inStream
                = new BufferedReader (new FileReader(fileName));
            String line = inStream.readLine();
            Scanner sc = new Scanner(line);
            n = sc.nextInt();
            m = sc.nextInt();
            map = new Cell[n][m];
            for(int i = 0; i < n; i++){
                line = inStream.readLine();
                for(int j = 0; j < m; j++){
                    switch (line.charAt(j)){
                    case '*' : map[i][j] = Cell.WALL; break;
                    case 'p' : map[i][j] = Cell.FOUND; break;
                    case '-' : map[i][j] = Cell.EXPLORED; break;
                    case ' ' : map[i][j] = Cell.PATH; break;
                    case 'S' : map[i][j] = Cell.START;
                        startr = i;
                        startc = j;
                        break;
                    case 'F' : map[i][j] = Cell.FINISH;
                        targetr = i;
                        targetc = j;
                        break;
                    default : System.out.println("Error in readMap"); System.exit(1);
                    }
                }
            }
        }
        catch (FileNotFoundException e) {
            System.out.println("IOERROR: File NOT Found: " + fileName);
            e.printStackTrace();
        } catch ( IOException e ) {
            System.out.println("IOERROR: " + e.getMessage());
            e.printStackTrace();
        }
    }

    public void displayMap(){
        for(int i = 0; i < n; i++){

            for(int j = 0; j < m; j++){
                switch (map[i][j]){
                case WALL : System.out.print('*');  break;
                case FOUND : System.out.print('p') ; break;
                case EXPLORED: System.out.print('-') ; break;
                case PATH : System.out.print(' ') ; break;
                case START : System.out.print('S') ; break;
                case FINISH : System.out.print('F') ; break;
                }
            }
            System.out.println();
        }
    }
    public static void main (String args[]) {
        Maze myM = new Maze();
        myM.readMap(args[0]);
        myM.displayMap();
        boolean hasPath = myM.path();
        if (hasPath) {
            System.out.println("A path was found!");
        } else{
            System.out.println("No path was found!");
        }
        myM.displayMap();
    }

    public boolean path(){
        boolean res = path(startr, startc);
        map[startr][startc] = Cell.START;
        return res;
    }

    private boolean path(int r, int c){
        if(map[r][c] == Cell.FINISH)
            return true;
        if((map[r][c] == Cell.EXPLORED) ||
           (map[r][c] == Cell.WALL))
            return false;
        map[r][c] = Cell.EXPLORED;
        int [][] dirs = {{-1,0}, {1,0},
                         {0,-1}, {0,1}};
        for (int d = 0; d<4; d++) {
            int i = r+dirs[d][0];
            int j = c+dirs[d][1];
            if(path(i,j)){
                map[r][c] = Cell.FOUND;
                return true;
            }
        }
        return false;
    }

}