[APS] Izminuvanje na Lavirint

Изминување на лавиринт Problem 2 (1 / 1)

Нека е даден совршен лавиринт (во форма како на аудиториските вежби - како влез од карактери). Ваша задача е да изгенерирате граф со листа на соседство (ненасочен и нетежински) од дадениот влез и да ја испечатите патеката од почетното (темето означено со S) до крајното теме (темето означено со Е).

Патеката ја печатите на следниот начин: ги печатите координатите на јазлите кои ги изминувате (т.е ги печатите позициите од влезот)

Име на класа: Lavirint




====================================================================================================================================

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Hashtable;
import java.util.Stack;

class Lavirint {



    static class Graph {

        int num_nodes; // broj na jazli
        int adjMat[][];  // matrica na sosednost

        public Graph(int num_nodes) {
            this.num_nodes = num_nodes;
            adjMat = new int[num_nodes][num_nodes];

            for(int i=0;i<this.num_nodes;i++)
                for(int j=0;j<this.num_nodes;j++)
                    adjMat[i][j]=0;
        }

        public Graph(int num_nodes, int[][] adjMat) {
            this.num_nodes = num_nodes;
            this.adjMat = adjMat;
        }


        int adjacent(int x,int y)
        {  // proveruva dali ima vrska od jazelot so indeks x do jazelot so indeks y
            return (adjMat[x][y]!=0)?1:0;
        }

        void addEdge(int x,int y)
        {  // dodava vrska megu jazlite so indeksi x i y
            adjMat[x][y]=1;
            adjMat[y][x]=1;
        }

        void deleteEdge(int x,int y)
        {
            // ja brise vrskata megu jazlite so indeksi x i y
            adjMat[x][y]=0;
            adjMat[y][x]=0;
        }

        public int getNum_nodes() {
            return num_nodes;
        }

        public void setNum_nodes(int num_nodes) {
            this.num_nodes = num_nodes;
        }



        @Override
        public String toString() {
            String ret="  ";
            for(int i=0;i<num_nodes;i++)
                ret+=i+" ";
            ret+="\n";
            for(int i=0;i<num_nodes;i++){
                ret+=i+" ";
                for(int j=0;j<num_nodes;j++)
                    ret+=adjMat[i][j]+" ";
                ret+="\n";
            }
            return ret;
        }


    }



    static class Maze {

        //Kje se koristi nenasocen graf implementiran so martica na sosednost
        //za pretstavuvanje na lavirintot
        //Teminjata vo grafot se samo indeksi
        //Iminjata na teminjata se preveduvaat vo broevi preku hash tabela
        //T.e. na pr. 1,1 kje se prevede vo 1 (1,1 kje se zacuva kako string)

        Graph g;
        int start_node; //indeks temeto koe e vlez
        int end_node; //indeks na temeto koe e izlez

        Hashtable<String,Integer> h;


        Hashtable<Integer,String> rehash;


        public Maze() {
            h = new Hashtable<String,Integer>();
            rehash = new Hashtable<Integer,String>();
        }

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

            int num_nodes = 0;

            String key;

            for(int i=1; i<rows; i++){
                for(int j=1; j<columns; j++){
                    if(in[i].charAt(j)!='#'){
                        key = i+","+j;
                        rehash.put(num_nodes+1,key);
                        h.put(key, num_nodes);
                        if(in[i].charAt(j)=='S')
                            start_node = num_nodes;
                        if(in[i].charAt(j)=='E')
                            end_node = num_nodes;
                        num_nodes++;
                    }
                }
            }

            g = new Graph(num_nodes);

            int x;
            int y;
            //generiranje na matrica na sosednost
            for(int i=1; i<rows; i++){
                for(int j=1; j<columns; j++){
                    if(in[i].charAt(j)!='#'){
                        //dali ima teme pred nego
                        if(in[i].charAt(j-1)!='#'){
                            x = h.get(i+","+j);
                            y = h.get(i+","+(j-1));
                            g.addEdge(x, y);
                        }
                        //dali ima teme posle nego
                        if(in[i].charAt(j+1)!='#'){
                            x = h.get(i+","+j);
                            y = h.get(i+","+(j+1));
                            g.addEdge(x, y);
                        }
                        //dali ima teme nad nego
                        if(in[i-1].charAt(j)!='#'){
                            x = h.get(i+","+j);
                            y = h.get((i-1)+","+j);
                            g.addEdge(x, y);
                        }
                        //dali ima teme pod nego
                        if(in[i+1].charAt(j)!='#'){
                            x = h.get(i+","+j);
                            y = h.get((i+1)+","+j);
                            g.addEdge(x, y);
                        }
                    }
                }
            }
        }

        void findPath(){
            boolean visited[] = new boolean[g.getNum_nodes()];
            for (int i = 0; i < g.getNum_nodes(); i++)
                visited[i] = false;
            visited[start_node] = true;
            Stack<Integer> s = new Stack<Integer>();
            s.push(start_node);

            int pom;
            while (!s.isEmpty() && s.peek()!=end_node) {
                pom = s.peek();
                int pom1 = pom;
                for (int i = 0; i < g.getNum_nodes(); i++) {
                    if(g.adjacent(pom,i)==1){
                        pom1 = i;
                        if(!visited[i])
                            break;
                    }
                }
                if(!visited[pom1]){
                    visited[pom1] = true;
                    //System.out.println(tmp.getIndex() + ": " + tmp.getInfo());
                    s.push(pom1);
                }
                else
                    s.pop();
            }
            if(s.isEmpty())
                System.out.println("Nema reshenie");
            else{
                Stack<Integer> os = new Stack<Integer>();
                while(!s.isEmpty())
                    os.push(s.pop());
                while(!os.isEmpty()){
                    int key = os.pop();
                    System.out.println(rehash.get(key+1));
                }


            }
        }



        public static void main(String args[]) throws IOException {
            Maze m = new Maze();
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            String line = in.readLine();
            String pom[] = line.split(",");
            int rows = Integer.parseInt(pom[0]);
            int columns = Integer.parseInt(pom[1]);

            String input[] = new String[rows];
            for(int i = 0; i < rows; i++){
                input[i] = in.readLine();
            }


            m.generateGraph(rows, columns, input);
            System.out.println("Pateka:");
            m.findPath();
/*

            String[] in = new String[rows];
            Maze m = new Maze();
            int rows = 6;
            int columns = 6;
            in[0] = "######";
            in[1] = "# # ##";
            in[2] = "# # S#";
            in[3] = "# # ##";
            in[4] = "# E  #";
            in[5] = "######";

            m.generateGraph(rows, columns, in);
            System.out.println("Pateka:");
            m.findPath();
*/



        }

    }



}