bfs(showHistory).java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.math.*;


/*
sample input 

> enter(row col) : 8 8
****S***
*......*
*..*****
*....*.*
****.*.*
*.G*...*
*......*
********

> output
****S***
*.RRR..*
*.R*****
*.RRR*.*
****R*.*
*.G*R..*
*.RRR..*
********

*/

public class Main {
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[][] map;
		System.out.print("enter(row col) : ");
		String[] str = br.readLine().split(" ");
		int row = -1;
		int col = -1;
		//enter text
		try{
			row = Integer.parseInt(str[0]);
			col = Integer.parseInt(str[1]);
		}catch(NumberFormatException e){
			System.out.println(e);
		}
		map = new String[row][col];
		int sx = -1;
		int sy = -1;
		int gx = -1;
		int gy = -1;

		for(int i = 0; i < row; i++){
			String tmp = br.readLine();
			for(int j = 0; j < col; j++){
				map[i][j] = tmp.substring(j,j+1);
				if(map[i][j].equals("S")){
					sx = i;
					sy = j;
				}
				if(map[i].equals("G")){
					gx = i;
					gy = j;
				}
			}
		}

		bfs(map,row,col,sx,sy);
	}

	static void bfs(String[][] map, int row, int col, int sx, int sy){
		int[] fromX = new int[row*col];
		int[] fromY = new int[row*col];
		int[] fromID = new int[row*col];
		Arrays.fill(fromX,Integer.MAX_VALUE);
		Arrays.fill(fromY,Integer.MAX_VALUE);

		boolean[][] footprint = new boolean[row][col];
		int[] nextX = new int[row*col];
		int[] nextY = new int[row*col];
		Arrays.fill(fromX,Integer.MAX_VALUE);
		Arrays.fill(fromY,Integer.MAX_VALUE);
		footprint[sx][sy] = true;
		nextX[0] = sx;
		nextY[0] = sy;

		for(int i = 0; i < row; i++){
			for(int j = 0; j < col; j++){
				if(map[i][j].equals("*"))
					footprint[i][j] = true;
			}
		}

		int dequeue = 0;
		int enqueue = 1;
		while(dequeue < enqueue){
			int x = nextX[dequeue];
			int y = nextY[dequeue];

			if(map[x][y].equals("G")){
				break;
			}
			
			// check left
			if(x-1 >= 0){
				if(!footprint[x-1][y]){
					footprint[x-1][y] = true;
					fromX[enqueue] = x;
					fromY[enqueue] = y;
					fromID[enqueue] = dequeue;
					nextX[enqueue] = x-1;
					nextY[enqueue] = y;
					enqueue++;
				}
			}
			// check right
			if(x+1 < row){
				if(!footprint[x+1][y]){
					footprint[x+1][y] = true;
					fromX[enqueue] = x;
					fromY[enqueue] = y;
					fromID[enqueue] = dequeue;
					nextX[enqueue] = x+1;
					nextY[enqueue] = y;
					enqueue++;
				}
			}
			// check upper
			if(y-1 >= 0){
				if(!footprint[x][y-1]){
					footprint[x][y-1] = true;
					fromX[enqueue] = x;
					fromY[enqueue] = y;
					fromID[enqueue] = dequeue;
					nextX[enqueue] = x;
					nextY[enqueue] = y-1;
					enqueue++;
				}
			}
			// check lower
			if(y+1 < col){
				if(!footprint[x][y+1]){
					footprint[x][y+1] = true;
					fromX[enqueue] = x;
					fromY[enqueue] = y;
					fromID[enqueue] = dequeue;
					nextX[enqueue] = x;
					nextY[enqueue] = y+1;
					enqueue++;
				}
			}
			
			dequeue++;
		}
		showHistory(fromX,fromY,fromID,dequeue,map);
	}

	static void showHistory(int[] fromX, int[] fromY, int[] fromID, int dequeue, String[][] map){
		int id = dequeue;
		while(id!=1){
			int x = fromX[id];
			int y = fromY[id];
			map[x][y] = "R";
			id = fromID[id];
		}
		showMap(map);
	}

	static void showMap(String[][] map){
		int len = map.length;
		System.out.println();
		for(int i = 0; i < len; i++){
			System.out.println(String.join("",map[i]));
		}
	}
}