//
//  Maze.java
//  MazeTest
//
//  Created by Gerhard Dueck on 11-02-08.
//  Copyright 2011 University of New Brunswick. All rights reserved.
//
import java.io.*;
import java.util.*;
enum Cell {
    WALL, FOUND, EXPLORED, PATH, START, FINISH  }
class Coord {
    public int r,c;
    public Coord(int _r, int _c) {r=_r; c=_c;}
}
public class StackMaze {

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

    private int startr, startc, targetr, targetc;

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

    private LinkedStack<Coord> todo;
    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 boolean path(){
        todo= new LinkedStack<Coord>();
        todo.push(new Coord(startr,startc));
        while (!todo.isEmpty()){
            Coord here=todo.pop();
            int r=here.r;
            int c=here.c;
            System.out.println("Exploring " + here.r + " " +here.c );
            if (visit(r-1,c) || visit(r,c-1) ||
                visit(r+1,c) || visit(r,c+1))
                return true;
        }
        return false;
    }
    private boolean visit(int i, int j){
        if (i<0 || i>n || j<0 || j>m)
            return false;

        if(map[i][j] == Cell.FINISH)
            return true;
        if(map[i][j] == Cell.PATH){
            System.out.println("Pushing " + i + " " + j );
            map[i][j]=Cell.EXPLORED;
            todo.push(new Coord(i,j));
        }
        return false;
    }

    public static void main (String args[]) {
        StackMaze myM = new StackMaze();
        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();
    }
}