Recursion의 응용 - 미로찾기 1

• Maze 미로찾기

현재 위치에서 출구까지 가는 경로가 있으려면

   1) 현재 위치가 출구이거나 혹은

   2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나

 

boolean findPath(x,y)
	if (x,y) is the exit
    	return true:
    else
    	for each eighbouring cell (x', y') of (x, y) do
        	if (x', y') is on the pathway
            	if findPath(x', y')
                	return true;
        else false;
}

boolean findPath(x,y)
	if (x,y) is the exit
    	return true:
    else
    	mark (x, y) as a visited cell;
    	for each eighbouring cell (x', y') of (x, y) do
        	if (x', y') is on the pathway and not visited
            	if findPath(x', y')
                	return true;
        else false;
}

boolean findPath(x,y)
	if (x,y) is either on the wall or a visited cell
    	return false:
    else if (x, y) is the exit:
     	return true:
    else
    	mark(x, y) as a visited cell:
    	for each eighbouring cell (x', y') of (x, y) do
            	if findPath(x', y')
                	return true;
        else false;
}

 

• class Maze

public class Maze {
	private static int N=8;
    private static int [][] maze = {
    	{0, 0, 0, 0, 0, 0, 0, 1},
        {0, 1, 1, 0, 1, 1, 0, 1},
        {0, 0, 0, 1, 0, 0, 0, 1},
        {0, 1, 0, 0, 1, 1, 0, 0},
        {0, 1, 1, 1, 0, 0, 1, 1},
        {0, 1, 0, 0, 0, 1, 0, 1}, 
        {0, 0, 0, 1, 0, 0, 0, 1},
        {0, 1, 1, 1, 0, 1, 0, 0}
};

private static final int PATHWAY_COLOUR = 0;
private static final int WALL_COULOUR = 1;
private static final int BLOKED_COULOUR = 2;
priavet static final int PATH_COLOUR = 3;


public static boolean findMazePath(int x, int y){
	if (x<0 || y<0 || y>=N)
    	return false;
    else if (maze[z][y] != PATHWAY_COLOUR)
    	return false;
    else if (x==N-1 && y==N-1){
    	maze[x][y]= PATH_COLOUR;
        return true;
     else{
     	maze[x][y] = PATH_COLOUR;
        if(findMazePath(z-q, y) || findMazePath(x, y+1) || findMazePath(x+1, y) || findMazePath(x, y-1)) {
        	return true;
        }
        maze[x][y] = BLOCKED_COLOUR;
        return false;
    }
}

public static void main(String [] args) {
	printMaze();
    findMazePath(0, 0);
    printMaze();
    }
}