import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.BreadthFirstPaths;

import java.util.ArrayList;


public class MazeSolver  {

	//private static int numMoves = 0; // Allows us to keep track of how many recursive calls to findPath are required to solve the maze.
    private String[][] maze;
    int numRows;
    int numCols;

    int numV = 0; //number of vertices/number of periods, O
    Graph graph;

    int sVertex = 0;
    int sRow = 0;
    int sCol = 0;
    int gVertex = 0;



    /**
     * Creates a 2D array of String, maze Precondition: mazeStr must begin with
     * the number of rows followed by a space, the the number of columns
     * followed by a space, and finally by a string representation of the maze,
     * with rows separated by the newline "\n". The maze string will contain one
     * "S", one "G", a "." for each open cell, and a "#" for each obstacle.
     *
     * @param mazeStr a string meeting the preconditions described above
     */
    public MazeSolver(String mazeStr) {
        int i = 0;
        int endIndex = mazeStr.indexOf(" ");
        this.numRows = Integer.parseInt(mazeStr.substring(i, endIndex));
        i = endIndex + 1;
        endIndex = mazeStr.indexOf(" ", i);
        this.numCols = Integer.parseInt(mazeStr.substring(i, endIndex));
        i = endIndex + 1; // i now points to the first char in first row of maze

        // Let's make sure our string maze has the proper number of characters in it...
        if (numRows * numCols != mazeStr.substring(i).length() - numRows + 1) {
            throw new IllegalArgumentException("mazeStr is not well-formed.");
        }

        // Now we build the maze from the maze string.
        this.maze = new String[numRows][numCols];  // DON'T FORGET to actually create the array!
        for (int row = 0; row < numRows; row++) {
            for (int col = 0; col < numCols; col++) {
            	String val = mazeStr.substring(i, i + 1);
            	if (val.equals(".") || val.equals("S") || val.equals("G")) numV++;
                maze[row][col] = val;
                i++;
            }
            i++; // this increment, after each row, skips the newline character '\n'
        }
    }

    /**
     * This helper method allows one to create a maze in a text editor. It
     * creates a string formed for use by the MazeSolver constructor.
     *
     * @param fName the name of a text file containing a maze
     * @return The maze string in the form of
     * "<numRows><space><numCols><space><line1>\n<line2>\n...<lastLine>"
     */
    public static String makeMazeStringFromFile(String fName) {
        String str = "";
        // build the mazeStr
        //String mazeStr = "" + rows + " " + cols + " ";
        // read the text file containing maze characters and append to mazeStr
        File file = new File(fName);
        Scanner reader = new Scanner(System.in);
        try {
            reader = new Scanner(file);
        } catch (FileNotFoundException e) {
            System.out.println("Maze file not found.");
        }
        String line1 = reader.nextLine();
        str = str + line1 + "\n";
        int numCols = line1.length();
        int numRows = 1;
        while (reader.hasNext()) {
            String line = reader.nextLine();
            str = str + line + "\n";
            if (line.length() > 0) {
                numRows++;
            }
        }

        String mazeStr = "" + numRows + " " + numCols + " " + str.substring(0, str.length());
        if (mazeStr.substring(mazeStr.length() - 1).equals("\n")) // did they press ENTER after the last line?
        {
            mazeStr = mazeStr.substring(0, mazeStr.length() - 1);  // drops the last "\n" character
        }
        reader.close();
        return mazeStr;
    }

    /**
     * Creates a 2D matrix view of the contents of the array maze
     * @return the contents of maze with rows separated by newline '\n'
     */
    @Override
    public String toString() {
        String str = "";
        for (String[] row : maze) {
            for (String val : row) {
                str += val;
            }
            str += "\n";
        }
        return str;
    }

    public void solve () {
    	createGraph();
     	runBFS();
    }

    public void createGraph() {
    	graph = new Graph(numV);

    	int v = -1;

    	for (int row = 0; row < numRows; row++) {
    		for (int col = 0; col < numCols; col++) {

    			if (isVertex(maze[row][col])) {
    				v++;

    				if (maze[row][col].equals("S")) {
    					sRow = row;
    					sCol = col;
    					sVertex = v;
    			    }
    				else if (maze[row][col].equals("G"))
    					gVertex = v;

    				if (row > 0 && 		     isVertex(maze[row - 1][col    ])) //check up
    					if (!adjContains( v, (v - verticesBetween(row - 1, col, row, col))))
        					graph.addEdge(v, (v - verticesBetween(row - 1, col, row, col)));

    				if (col < numCols - 1 && isVertex(maze[row    ][col + 1])) //check right
    					if (!adjContains( v, v + 1))
    						graph.addEdge(v, v + 1);

    				if (col > 0 && 	 	     isVertex(maze[row    ][col - 1])) //check left
    					if (!adjContains( v, v - 1))
    						graph.addEdge(v, v - 1);

    				if (row < numRows - 1 && isVertex(maze[row + 1][col    ])) //check down
    					if (!adjContains( v, (v + verticesBetween(row, col, row + 1, col))))
    						graph.addEdge(v, (v + verticesBetween(row, col, row + 1, col)));
    			}
    		}
    	}
    }

    //GRAPH METHODS

    public boolean isVertex (String c) {
    	if (c.equals(".") || c.equals("S") || c.equals("G")) return true;
    	else return false;
    }

    public boolean adjContains (int v, int hypV) {
    	for (int e : graph.adj(v)) {
    		if  (e == hypV) return true;
    	}
    	return false;
    }

    public int verticesBetween (int x1, int y1, int x2, int y2) {
    	int v = 0;

    	int colSet = y1;

    	for (int row = x1; row < numRows; row++) {
    		if (row == x1 + 1) colSet = 0;
    		for (int col = colSet; col < numCols; col++) {
    			if (row == x1 && col == y1);
    			else if (isVertex(maze[row][col]))
    				v++;
    			if (row == x2 && col == y2) return v;
    		}
    	}
    	return v;
    }

    //DFS METHODS

	public void runBFS () {
    	BreadthFirstPaths BFS = new BreadthFirstPaths(graph, sVertex);
    	Iterable<Integer>  path     = BFS.pathTo(gVertex);

    	if (!BFS.hasPathTo(gVertex))
    		System.out.println("this maze is unsolvable.");
    	else {
    		ArrayList<Integer> pathCopy = new ArrayList<Integer>();

    		for (Integer v : path)
    			pathCopy.add(v);

    		int v = -1;

    		for (int row = 0; row < numRows; row++) {
    			for (int col = 0; col < numCols; col++) {
    				if (!maze[row][col].equals("#")) {
    					v++;
    					if (maze[row][col].equals("."))
    						if (pathCopy.contains(v))
    							maze[row][col] = "+";
    				}
    			}
    		}
    	}
    }

	public void printWithColor () {
		final String ANSI_RESET = "\u001B[0m";
		final String ANSI_PURPLE = "\u001B[35m";

        for (int row = 0; row < numRows; row++) {
        	for (int col = 0; col < numCols; col++) {
        		String c = maze[row][col];
        		if (c.equals("+"))
        			System.out.print(ANSI_PURPLE + "+" + ANSI_RESET);
        		else
        			System.out.print(c);
        	}
        	System.out.println();
        }
	}

	/**
     * @param args the command line arguments
     */
	public static void main (String[] args) throws FileNotFoundException {
		MazeSolver ms = new MazeSolver("6 6 ##S###\n#....#\n#....#\n#....#\n#..#.#\n#G####");
        System.out.println(ms);
        ms.solve();
        System.out.println(ms);

		/*System.out.println("\nSolving maze in maze0.txt");
        ms = new MazeSolver(makeMazeStringFromFile("maze0.txt"));
        System.out.println(ms);
        ms.solve();
        System.out.println(ms);*/

        System.out.println("\nSolving maze in maze1.txt");
        ms = new MazeSolver(makeMazeStringFromFile("maze1.txt"));
        System.out.println(ms);
        ms.solve();
        System.out.println(ms);

        System.out.println("\nSolving maze in maze2.txt");
        ms = new MazeSolver(makeMazeStringFromFile("maze2.txt"));
        System.out.println(ms);
        ms.solve();
        System.out.println(ms);

        System.out.println("\nSolving maze in maze3.txt");
        ms = new MazeSolver(makeMazeStringFromFile("maze3.txt"));
        System.out.println(ms);
        ms.solve();
        System.out.println(ms);

        System.out.println("\nSolving maze in maze4.txt");
        ms = new MazeSolver(makeMazeStringFromFile("maze4NoSolution.txt"));
        System.out.println(ms);
        ms.solve();
        System.out.println(ms);
	}
}

//comment of sample main() runs

/*
##S###
#....#
#....#
#....#
#..#.#
#G####

##S###
#.+..#
#.+..#
#.+..#
#++#.#
#G####


Solving maze in maze1.txt
####################
#.................##
#..................#
S..................#
##################.#
G...#..............#
###.#..............#
###................#
###...............##
##................##
##.#################
##..################
###.################
###.#..............#
###.########.#######
#.................##
#.................##
##...............###
##................##
####################

####################
#.................##
#..................#
S++++++++++++++++++#
##################+#
G+++#.............+#
###+#.............+#
###++++++++++++++++#
###...............##
##................##
##.#################
##..################
###.################
###.#..............#
###.########.#######
#.................##
#.................##
##...............###
##................##
####################


Solving maze in maze2.txt
####################
#.................##
#..................#
S..................#
##################.#
#...#..............#
###.#..............#
###................#
###...............##
##................##
##.#################
##..################
###.################
##..#..............#
##.#########.#######
#.................##
#.................##
##...............###
##................##
#################G##

####################
#.................##
#..................#
S++++++++++++++++++#
##################+#
#...#.............+#
###.#.............+#
###..............++#
###..............+##
##++++++++++++++++##
##+#################
##++################
###+################
##++#..............#
##+#########.#######
#.+...............##
#.+...............##
##+..............###
##++++++++++++++++##
#################G##


Solving maze in maze3.txt
####################
#.................##
#..................#
#..................#
##################.#
#...#..............#
###.#..............#
###................#
###...............##
##................##
##.#################
##..################
###.################
##..#..............#
##.#########.#######
#.................##
#.................##
##...............###
##................##
##S##############G##

####################
#.................##
#..................#
#..................#
##################.#
#...#..............#
###.#..............#
###................#
###...............##
##................##
##.#################
##..################
###.################
##..#..............#
##.#########.#######
#.................##
#.................##
##...............###
##++++++++++++++++##
##S##############G##


Solving maze in maze4.txt
####################
#.................##
#..................#
#..................#
##################.#
#...#..............#
###.#..............#
###................#
###...............##
##................##
##.#################
##..################
###.################
##..#..............#
##.#########.#######
#.................##
#.................##
##...............###
##..............#.##
##S##############G##

this maze is unsolvable.
####################
#.................##
#..................#
#..................#
##################.#
#...#..............#
###.#..............#
###................#
###...............##
##................##
##.#################
##..################
###.################
##..#..............#
##.#########.#######
#.................##
#.................##
##...............###
##..............#.##
##S##############G##
*/