package grafy;

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

public class Labirynt{
    static W tab[][] = new W[100][100];
    
    static void BFS(List<W> graf, int s){
        List<W> list = new ArrayList<W>();
        for(int i=0;i<graf.size();++i){
                graf.get(i).setWhite(graf.get(i));
                graf.get(i).setPoprzednik(null);
                graf.get(i).setOdleglosc(graf.get(i), -1);
        }
        graf.get(s).setGray(graf.get(s));
        graf.get(s).setOdleglosc(graf.get(s),0);
        graf.get(s).setPoprzednik(null);
        list.add(graf.get(s));
        while(!list.isEmpty()){
                W u = list.get(0);
                list.remove(0);
                for(Kr v: u.laczenia)
                {
                        if(v.w.isWhite(v.w)){
                                v.w.setGray(v.w);
                                v.w.setOdleglosc(v.w, u.getOdleglosc(u)+1);
                                v.w.setPoprzednik(u);
                                list.add(v.w);
                        }
                }
                u.setBlack(graf.get(u.number));
        }
}
    
	static void AddConnect(W w, W[][] tab){
		int x=w.x,
			y=w.y;
		Kr kr;
		if(tab[x-1][y]!=null){
			kr = new Kr();
			kr.w=tab[x-1][y];
			w.addConnection(kr);
		}
		if(tab[x+1][y]!=null){
			kr = new Kr();
			kr.w=tab[x+1][y];
			w.addConnection(kr);
		}
		if(tab[x][y-1]!=null){
			kr = new Kr();
			kr.w=tab[x][y-1];
			w.addConnection(kr);
		}
		if(tab[x][y+1]!=null){
			kr = new Kr();
			kr.w=tab[x][y+1];
			w.addConnection(kr);
		}
	}
	static void MakePath(W s, W k){
		W w=k;
		while(w!=s){
			w.getPoprzednik(w).c='+';
			w=w.getPoprzednik(w);
		}
	}
	static void PrintPath(List<W> graf, W ws, W wk){
		MakePath(ws, wk);
		for(int i=0;i<50;++i){
			for(int j=0;j<50;++j){
				System.out.print(tab[i][j].c);
			}
			System.out.println();
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(new File("H:\\java\\workspace\\klasa3\\src\\grafy\\labirynt.txt"));
		List<W> graf = new ArrayList<W>();
        W w; Kr kr;
//        w.BFS(graf, 0);
//        sc.close();
        int Sx =0, Sy =0, Kx=0, Ky=0, y=0;
//        W tab[][] = new W[100][100];
        for(W[] t: tab){
        	for(W z: t){
        		z=null;
        	}
        }
        int asd=0;
        while(sc.hasNext()){
        	
        	String str = sc.nextLine();
        	if(str.charAt(0)=='*')continue;
        	for(int x=0; x<str.length();++x){
        		if(str.charAt(x)=='#')continue;
        		else if(str.charAt(x)=='S'){
        			Sx=x;
        			Sy=y;
        			w = new W();
        			w.x=x;
        			w.y=y;
        			w.setNumber(asd);
        			++asd;
        			tab[x][y]=w;
        			graf.add(w);
        		}
        		else if(str.charAt(x)=='W'){
        			Kx=x;
        			Ky=y;
        			w = new W();
        			w.x=x;
        			w.y=y;
        			w.setNumber(asd);
        			++asd;
        			tab[x][y]=w;
        			graf.add(w);
        		}
        		else if(str.charAt(x)=='.'){
        			w = new W();
        			w.x=x;
        			w.y=y;
        			w.setNumber(asd);
        			++asd;
        			tab[x][y]=w;
        			graf.add(w);
        		}
        	}
        	++y;
        }
        for(W[] t: tab){
        	for(W z: t){
        		if(z!=null)
        			AddConnect(z, tab);
        	}
        }
        w =tab[Sx][Sy];
        int source = tab[Sx][Sy].getNumber(tab[Sx][Sy]);
        
        BFS(graf, source);
        W ws=tab[Sx][Sy],
        	wk=tab[Kx][Ky];
        PrintPath(graf,ws,wk);
        sc.close();
	}

}

########################################
#S.##..#.....###.................##....#
##.#.....#.#...#.######.###..###.#..####
#..#.###.#.#.###.#....###.##.#.........#
##...#.###.#.#...#.#.##......###########
####.....###.#.###.#.#..#..#..#........#
#.....##.#...#.....#.##.#.############.#
#####..###.#########.#..#.#............#
#........#.#.........##.#.##.###.#####.#
#.###.##.#.#.#######..#.#..#.#.#.....#.#
#...#..#.#.#.#........#.####.#.#####.#.#
###.####.#.#.###.#.#..#......#.......#.#
#...#....#.#.....#######.#####.#####.#.#
###.#.#.##.#####.#.....#.......#.....#.#
#...###....###.#.#.#.#.###############.#
#.#...########.#.#.#.#.................#
###.#.#........#.#.#########.###########
#...#....#####.#.#...#.....#.......#...#
#.########...###.#.#.#.#####.#.###.#.###
#..........#.....#.#.........#...#....W#
########################################
*