import java.awt.*;
import javax.swing.*;

public class Maze2DArray extends JApplet {

    int rows, cols, scale;  
    double wallProbability;  
    	
    public void init() {

	String input;

	input = JOptionPane.showInputDialog("Enter # of rows","100");
	rows = Integer.parseInt(input);
	
	input = JOptionPane.showInputDialog("Enter # of columns","100");
	cols = Integer.parseInt(input);

	input = JOptionPane.showInputDialog("Enter probabilty of 'wall'","0.5");
	wallProbability = Double.parseDouble(input);
	if (wallProbability<0 || wallProbability>1) {
	    JOptionPane.showInputDialog(null,"Sorry dude. wall probability must be >=0 and <=1");
	    System.exit(1);
	}

	input = JOptionPane.showInputDialog("Enter scale factor","10");
	scale = Integer.parseInt(input);
    }

    public void paint(Graphics g) {
        super.paint(g);  
        	
    	int [][] maze = new int[rows][cols];   //initalized to 0: "clear"
    	
    	for (int i=0; i<rows; i++) 
	    for (int j=0; j<cols; j++) 
	    	if (Math.random() <= wallProbability) {
	            maze[i][j] = 1; //"wall"
	            g.fillRect(j*scale,i*scale,scale,scale);
	    	}
	    	
        //see how far can travel from center
        int r, c,  cheese=10;
        int up, down, left, right;
        int startR, startC;
        boolean trapped=false;
        
        r = startR = cols/2;
	c = startC = rows/2;
	g.setColor(Color.RED);
	maze[r][c] = cheese++; //"visited"  put a cheese
	g.fillRect(c*scale,r*scale,scale,scale);
	
	do {
	    //try to move into a clear neighboring position
	    if (c>0 && maze[r][c-1] == 0) { //left is clear
	        c--;
	        maze[r][c] = cheese++; //"visited"  put a cheese
	        g.fillRect(c*scale,r*scale,scale,scale);
	    }
	    else if (c<cols-1 && maze[r][c+1] == 0) { //right
	        c++;
	        maze[r][c] = cheese++; //"visited"  put a cheese
	        g.fillRect(c*scale,r*scale,scale,scale);
	    }
	    else if (r>0 && maze[r-1][c] == 0) { //up
	        r--;
	        maze[r][c] = cheese++; //"visited"  put a cheese
	        g.fillRect(c*scale,r*scale,scale,scale);
	    }
	    else if (r<rows-1 && maze[r+1][c] == 0) { //down
	        r++;
	        maze[r][c] = cheese++; //"visited"  put a cheese
	        g.fillRect(c*scale,r*scale,scale,scale);
	    }
	    //no way is clear, so backup to most recently cheesed neighbor (where you came from)
	    else {
	    	maze[r][c] = 2; //"deadend".  as if a wall.
	    	//which nbor is the one we came from
	    	if (c>0)
	    	    left = maze[r][c-1];
	    	else
	    	    left = -1;
	    	if (c<cols-1)
	    	    right = maze[r][c+1];
	    	else
	    	    right = -1;
	    	if (r>0)
	    	    up = maze[r-1][c];
	    	else
	    	    up = -1;
	    	if (r<rows-1)
	    	    down = maze[r+1][c];
	    	else
	    	    down = -1;
	    	if (up>down && up>left && up>right)  //came from up nbor
	    	    r--;  //step back into there
	    	else if (down>up && down>left && down>right)  //came from down nbor
	    	    r++;  	    	
	    	else if (left>up && left>down && left>right)  //came from left nbor
	    	    c--;  	    	
	    	else if (right>up && right>down && right>left)  //came from right nbor
	    	    c++;  	    	       
	    	
	    }
	    //if backedup to start and no moves available, trapped
	    if (r==startR && c==startC && 
	    	maze[r][c-1]!=0 && maze[r][c+1]!=0 && maze[r-1][c]!=0 && maze[r+1][c]!=0)
	    	trapped = true;
	    	
	} while (!trapped);
	
	g.setColor(Color.BLUE);
	g.fillRect(0,0,20,20);    //done signal
	   	
    }    
}