import java.util.*;
import java.awt.*;
 
public class MazeApplet extends java.applet.Applet 
  {
   int rows;
   int columns;
   int rowpos;
   int colpos;
   int finished_start;
   int newfound;
   int len;
   int fontsize;
   int seed;
   Random rd;
   byte[] mazedata;
   Color colour;
   Color background;
 
   public void start()
     {
      create();
     }
   public void init()
     {
      int r, c;
      char ch = 0;
      String s1 = getParameter("rows");
      String s2 = getParameter("cols");
      String s3 = getParameter("size");
      String s4 = getParameter("color");
      String s5 = getParameter("background");
 
      int i = 0;
 
      if (s1 == null || s2 == null)
         r = c = 20;
      else
        {
         r = Integer.parseInt(s1);
         c = Integer.parseInt(s2);
        }
      if (s3 == null)
        fontsize = 12;
      else
        fontsize = Integer.parseInt(s3);
 
      seed = (int)(new Date().getTime());
      colour = htmlToColor(s4);
      background = htmlToColor(s5);
 
      setBackground(background);
      
 
      finished_start = 0;
      rows = r;
      columns = c;
      len = rows * columns;
      rd = new Random();
      rowpos = Math.abs(rd.nextInt()) % rows; // choose start pos.
      colpos = Math.abs(rd.nextInt()) % columns;
      mazedata = new byte[len];        // allocate maze data
      for (i = 0; i < len; i++)
        mazedata[i] = 15; // initialize walls
 
      mazedata[rowpos * columns + colpos] |= 64;  // mark as used
 
      return;
     }
   protected void finalize()
     {
      return;
     }
 
   void create()
     {
      int badfind = 0;
      int dx, dy;
 
      while (finished() == 0)
        {
 
         if (newfound == 0)
           badfind++;
         else
           badfind = 0;
 
        dx = dy = 0;
        if (rd.nextInt() % 2 == 0)
           dx = (Math.abs(rd.nextInt()) % 2) * 2 - 1; // get either 1 or -1
        else
           dy = (Math.abs(rd.nextInt()) % 2) * 2 - 1; // get either 1 or -1
 
        // but wait...what if it's taking a long time?
        if (badfind > 20)
          {
           dx = dy = 0;         // guide toward first unused block...
           if (finished_start % columns < colpos)
              dx = -1;
           else if ((int)(finished_start / columns) < rowpos)
              dy = -1;
           else if (finished_start % columns > colpos)
              dx = 1;
           else
              dy = 1;
          }
 
        if (fillblock(rowpos + dy, colpos + dx) != 0)
          {
           // not out of bounds
           rowpos += dy;
           colpos += dx;
          }
        }
           
      // maze is now finished, so take out entry and exits
 
      mazedata[0] ^= 1;
      mazedata[len-1] ^= 4;
 
     }
 
   int finished()
     {
      for (int i = finished_start; i < len; i++)
        {
         finished_start = i;
         if (mazedata[i] < 64) // if unused block found
            return 0;          // this also keeps f_s intact..
        }
      return 1;  // 100% used blocks
     }
   int fillblock(int newrow, int newcol)
     {
      int dx, dy;
      int direction = 4;
 
      newfound = 0;
 
      if (newrow < 0 || newrow >= rows || newcol < 0 || newcol >= columns)
         return 0; // can't move there!
      if (mazedata[newrow * columns + newcol] >= 64) // if used already
         return 1; // return success, but don't fill
 
      dx = newcol - colpos;
      dy = newrow - rowpos;
 
      if (dy == -1)
        direction = 0;
      else if (dx == -1)
        direction = 1;
      else if (dy == 1)
        direction = 2;
      else if (dx == 1)
        direction = 3;
      else
        {
         System.out.println("Something is wrong.");
         System.out.println("dx,dy = " + dx + " " + dy);
         System.out.println("rp, cp = " + rowpos + " " + colpos);
         System.out.println("nr, nc = " + newrow + " " + newcol);
 
         return 0;
        }
 
      newfound = 1; // for tracking..was a new block found?
      mazedata[newrow * columns + newcol] |= 64; // mark it
      mazedata[rowpos * columns + colpos] &= 255 - power(2,direction);
      mazedata[newrow * columns + newcol] &= 255 - power(2,(direction+2)%4);
         // take out wall from both blocks using bit operators
 
      return 0;
     }
 
   public void paint(Graphics g)
     {
      int j, k;
      int xpos = 0, ypos = 0;
      
      g.clearRect(0, 0, getSize().width, getSize().height);
      Font f = new Font("Courier", Font.PLAIN, fontsize);
      g.setFont(f);
      g.setColor(colour);
 
      for (k = 0; k < rows; k++)
        {
         for (j = 0; j < columns; j++)
           {
            if ((mazedata[k * columns + j] & 1) == 1)
               g.drawLine(j * fontsize, k * fontsize, (j+1) * fontsize, k * fontsize);
            if ((mazedata[k * columns + j] & 2) == 2)
               g.drawLine(j * fontsize, k * fontsize, j * fontsize, (k+1) * fontsize);
           }
        }
 
      k = rows - 1;
      for (j = 0; j < columns; j++)
        {
         if ((mazedata[k * columns + j] & 4) == 4)
            g.drawLine(j * fontsize, (k+1)*fontsize, (j+1)*fontsize, (k+1)*fontsize);
        }
 
      g.drawLine(columns * fontsize, 0, columns * fontsize, rows * fontsize);
 
      return;
     }
 
   public int status()
     {
      System.out.print("rows = " + rows + ", cols = " + columns);
      System.out.print(", len = " + len + ", rowpos = " + rowpos);
      System.out.print(", colpos = " + colpos + "finished_start = ");
      System.out.print(finished_start + "\n");
 
      return 0;
     }
   public static int power(int base, int exp)
     {
      int result = 1;
 
      for (int i = 0; i < exp; i++)
        result *= base;
      return result;
     }
 
   public Color htmlToColor(String s)
     {
      Color colour;
      char ch;
      int i;
      int red = 0, green = 0, blue = 0;
 
      if (s == null)
        colour = Color.black;
      else
       {
        ch = 0;
        for (i = 0; i < s.length(); )
          {
           ch = s.charAt(i++);
           if (ch == ' ') break;
           red *= 10;
           red += ch - '0';
          }
        for (; i < s.length(); )
          {
           ch = s.charAt(i++);
           if (ch == ' ') break;
           green *= 10;
           green += ch - '0';
          }
        for (; i < s.length(); )
          {
           ch = s.charAt(i++);
           if (ch == ' ') break;
           blue *= 10;
           blue += ch - '0';
          }
        colour = new Color(red, green, blue);
 
       }
 
      return colour;
     }
 
  }