Maze.java

package lavirint;

import java.util.HashMap;
import java.util.Stack;

public class Maze {

    int start_node;
    int end_node;
    Graph<Integer> graph;

    public Maze() {
    }

    public void solve(String[] maze) {
        generateGraph(maze.length, maze[0].length(), maze);
        findPath();
    }

    private void generateGraph(int rows, int columns, String[] maze) {

        String key;
        int node = 0;
        HashMap<String, Integer> h = new HashMap<String, Integer>();

        for (int i = 1; i < rows-1; i++) {
            for (int j = 1; j < columns-1; j++) {

                char c = maze[i].charAt(j);
                if (c != '#') {
                    key = i+","+j;
                    h.put(key, node);

                    if (c == 'S') {
                        start_node = node;
                    }
                    if (c == 'E') {
                        end_node = node;
                    }

                    node++;
                }

            }
        }

        graph = new Graph<Integer>(node);
        int x, y;

        for (int i=1; i<rows-1; i++) {
            for (int j=1; j<columns-1; j++) {

                char c = maze[i].charAt(j);

                if (c != '#') {

                    if (maze[i].charAt(j+1) != '#') {
                        x = h.get(i+","+j);
                        y = h.get(i+","+(j+1));
                        graph.addEdge(x, y);
                    }

                    if (maze[i].charAt(j-1) != '#') {
                        x = h.get(i+","+j);
                        y = h.get(i+","+(j-1));
                        graph.addEdge(x, y);
                    }

                    if (maze[i+1].charAt(j) != '#') {
                        x = h.get(i+","+j);
                        y = h.get((i+1)+","+j);
                        graph.addEdge(x, y);
                    }

                    if (maze[i-1].charAt(j) != '#') {
                        x = h.get(i+","+j);
                        y = h.get((i-1)+","+j);
                        graph.addEdge(x, y);
                    }
                }
            }

        }

    }



    private void findPath() {

        Stack<Integer> s = new Stack<Integer>();
        boolean checked[] = new boolean[graph.getNum_nodes()];
        int tmp1, tmp2;

        for (int i = 0; i < checked.length; i++) {
            checked[i] = false;
        }

        s.push(start_node);
        checked[start_node] = true;

        while (!s.isEmpty() && (s.peek() != end_node)) {

            tmp1 = s.peek();
            tmp2 = tmp1;

            for (int i = 0; i < graph.getNum_nodes(); i++) {
                if (graph.adjacent(tmp1, i) == 1) {
                    tmp2 = i;

                    if (!checked[i]) {
                        break;
                    }
                }
            }

            if (!checked[tmp2]) {
                s.push(tmp2);
                checked[tmp2] = true;
            } else {
                s.pop();
            }

        }

        Stack<Integer> inverted = new Stack<Integer>();

        while (!s.isEmpty()) {
            inverted.push(s.pop());
        }

        while (!inverted.isEmpty()) {
            System.out.println(inverted.pop());
        }


    }

}