//
//  Maze.java
//  MazeTest
//
//  Created by Gerhard Dueck on 11-02-08.
//  Copyright 2011 University of New Brunswick. All rights reserved.
//  Modified by David Bremner 11-02-23 to compute distances.
//  Further modified by db 11-03-13 to use a queue, and visit every
//  square only once.

import java.io.*;
import java.util.*;
import java.lang.Math;

enum Cell {
    WALL,  PATH, START, FINISH  }

class Coord {
    public int r,c;
    public Coord(int _r, int _c) {r=_r; c=_c;}
}

public class StackMaze2 {

    private Cell[][] map;
    private int[][] distance;
    private LinkedStack<Coord> todo;
    int n,m; // n x m map

    private int startr, startc, targetr, targetc;

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

    public int getDistance(){
        return distance[targetr][targetc];
    }

    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];
            distance = new int[n][m];
            for(int i = 0; i < n; i++){
                line = inStream.readLine();
                for(int j = 0; j < m; j++){
                    distance[i][j]=Integer.MAX_VALUE;
                    switch (line.charAt(j)){
                    case '*' : map[i][j] = Cell.WALL; 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 PATH :
                    if (distance[i][j]<Integer.MAX_VALUE){
                        System.out.print(Character.forDigit(distance[i][j],16));
                    } else {
                        System.out.print(' ') ;
                    }

                    break;
                case START : System.out.print('S') ; break;
                case FINISH : System.out.print('F') ; break;
                }
            }
            System.out.println();
        }
    }

    public void explore(){
        todo = new LinkedStack<Coord>();

        distance[startr][startc]=0;

        todo.push(new Coord(startr, startc));
        while(!todo.isEmpty()){
            Coord here = todo.pop();

            int r = here.r;
            int c = here.c;
            int length = distance[r][c];

            visit(r-1,c,length+1);
            visit(r+1,c,length+1);
            visit(r,c-1,length+1);
            visit(r,c+1,length+1);
        }
    }
    private void visit(int i, int j,int length){
        if (i<0 || i>n || j<0 || j>m)
            return;

        if (map[i][j]==Cell.WALL)
            return;
        if (distance[i][j]==Integer.MAX_VALUE){
            distance[i][j]=length;
            todo.push(new Coord(i,j));
        }
    }
    public static void main (String args[]) {
        StackMaze2 myM = new StackMaze2();
        myM.readMap(args[0]);
        myM.displayMap();
        myM.explore();
        System.out.println("\nDistance= "+myM.getDistance()+"\n");
        myM.displayMap();
    }

}