/* Bridges Source Code          */

/* By Dick Christoph April 1998 */

/* dchristo@minn.net            */

/* www1.minn.net/~dchristo      */



import java.applet.*;

import java.awt.*;

import java.io.*;



public class Bridges extends Applet {

  public static final int MAXSCREENX = 340;

  public static final int MAXSCREENY = 340;

  public static final int MAXROWS = 17;

  public static final int MAXCOLS = 17;

  public static final int NOTOWER = 0;

  public static final int BLUETOWER = 1, BLUE = 1;

  public static final int REDTOWER = 2, RED = 2;

  public static final int ROW = 0;

  public static final int COL = 1;



  public static final int UP = 1;

  public static final int RIGHT = 2;

  public static final int LEFT = 3;

  public static final int DOWN = 4;



  public static int board[][], whoseTurn;

  static BridgeCanvas cnv1;

  static Label turnMsg, statusMsg;

  Button newGameButton;

  Panel p, p1;



  static boolean redWins, blueWins, debug;



  public static final int MAXSTEPS = 10000;

  public static final int MAXOPTIONS = 200;

  public static final int MAXPATHLIST = 32;

  public static boolean visited[][];

  public static boolean consider[][];

  public static Option optionList[];

  public static Step steps[];

  public static int minSteps[][];

  public static PathList bluePathList[], redPathList[];

  public static int optionTop, firstFreeStep, bluePathListTop, redPathListTop;

  public static double stepCounter;

  public static double maxSteps, maxOptions, maxPathList, maxMoves;



  public void init()

  { 

    setLayout(null);

    resize(MAXSCREENX,MAXSCREENY+60);

    addNotify();



    debug = false;

    cnv1 = new BridgeCanvas();

    add(cnv1);

    cnv1.reshape(0,0,MAXSCREENX, MAXSCREENY);



    p = new Panel();

    turnMsg = new Label("");

    turnMsg.setAlignment(Label.CENTER);

    p.add(turnMsg);

    whoseTurn = BLUE;

    toggleTurnMsg();

    p.reshape(0,MAXSCREENY,MAXSCREENX,30);

    add(p);

    p1 = new Panel();

    newGameButton = new Button("New Game");

    p1.add(newGameButton);

    if (debug)

    { statusMsg = new Label("");

      statusMsg.setAlignment(Label.CENTER);

      p1.add(statusMsg);

    }

    p1.reshape(0,MAXSCREENY+30,MAXSCREENX,30);

    add(p1);

    initBoard();

    setupMem();

    cnv1.repaint();

  }



  public boolean action(Event e, Object arg)

  { Object source = e.target;

    if (source == newGameButton)

    { initBoard();

      cnv1.repaint();

    }

    return true;

  }



  public void destroy() {

  }



  public void initBoard()

  { int r, c;

    redWins = false;

    blueWins = false;

    whoseTurn = BLUE;

    toggleTurnMsg();

    if (debug)

      statusMsg.setText("");

    maxSteps = 0;

    maxOptions = 0;

    maxPathList = 0;

    maxMoves = 0;



    board = new int[MAXROWS][MAXCOLS];



    for (r = 0; r < MAXROWS; r++)

    { for (c = 0; c < MAXCOLS; c++)

      { board[r][c] = NOTOWER;

        if ((r % 2) == 0)   /* even row */

        { if ((c % 2) == 1)   /* odd col */

          { board[r][c] = BLUETOWER;

        } }

        else  /* odd row */

        { if ((c % 2) == 0)   /* even col */

          { board[r][c] = REDTOWER;

    } } } }

  }



  public static void toggleTurnMsg()

  {

    if (whoseTurn == BLUE)

    { whoseTurn = RED;

      turnMsg.setText("Red - It is your Move");

    }

    else

    { whoseTurn = BLUE;

      turnMsg.setText("Blue - It is your Move");

    }

  }



  public static boolean toggleBox(int r, int c)

  { boolean rv;



    if (board[r][c] == NOTOWER)

    { rv = true;

      if (whoseTurn == BLUE)

      { board[r][c] = BLUETOWER;

        toggleTurnMsg();

        determineBlueProgress();

      }

      else

      { board[r][c] = REDTOWER;

        toggleTurnMsg();

        determineRedProgress();

      }

    }

    else

      rv = false;

    return(rv);

  }



  public static void determineBlueProgress()

  { int r,c, r1, c1, tryTop, tryPtr;

    int tries[][];



    visited = new boolean[MAXROWS][MAXCOLS];

    for (r = 0; r < MAXROWS; r++)

      for (c = 0; c < MAXCOLS; c++)

        visited[r][c] = false;



    tries = new int[MAXROWS*MAXCOLS][2];

    blueWins = false;



    r = 0;

    for (c = 1; c < MAXCOLS && (!blueWins); c = c + 2)

    { /* board[0][c] = BLUETOWER */

      if (!visited[0][c])

      { tryTop = 0;

        tryPtr = 0;

        tries[tryTop][ROW] = 0;

        tries[tryTop++][COL] = c;

        while ((tryPtr < tryTop) && (!blueWins))

        { r1 = tries[tryPtr][ROW];

          c1 = tries[tryPtr][COL];

          visited[r1][c1] = true;

          if (r1 == MAXROWS - 1)

            blueWins = true;

          else

          { if ((r1 - 1) >= 0)  /* check up */

            { if ((!visited[r1-1][c1]) && (board[r1-1][c1] == BLUETOWER))

              { tries[tryTop][ROW] = r1-1;

                tries[tryTop++][COL] = c1;

            } }

            /* check down */

            if ((!visited[r1+1][c1]) && (board[r1+1][c1] == BLUETOWER))

            { { tries[tryTop][ROW] = r1+1;

                tries[tryTop++][COL] = c1;

            } }

            if ((c1 - 1) >= 0)  /* check left */

            { if ((!visited[r1][c1-1]) && (board[r1][c1-1] == BLUETOWER))

              { tries[tryTop][ROW] = r1;

                tries[tryTop++][COL] = c1-1;

            } }

            /* check right */

            if ((c1 + 1) < MAXCOLS)  

            { if ((!visited[r1][c1+1]) && (board[r1][c1+1] == BLUETOWER))

              { tries[tryTop][ROW] = r1;

                tries[tryTop++][COL] = c1+1;

          } } }

          tryPtr++;

        }

      }

    }

    if (blueWins)

    { turnMsg.setText("Blue Wins");

      if (debug)

        statusMsg.setText("Blue Wins" + " MS: " + maxSteps + " MO: " + maxOptions + " MP: " + maxPathList + " MM: " + maxMoves);

    }

  }



  public static void determineRedProgress()

  { int r,c, r1, c1, tryTop, tryPtr;

    int tries[][];



    visited = new boolean[MAXROWS][MAXCOLS];

    for (r = 0; r < MAXROWS; r++)

      for (c = 0; c < MAXCOLS; c++)

        visited[r][c] = false;



    tries = new int[MAXROWS*MAXCOLS][2];

    redWins = false;



    c = 0;

    for (r = 1; r < MAXROWS && (!redWins); r = r + 2)

    { /* board[r][0] = REDTOWER */

      if (!visited[r][0])

      { tryTop = 0;

        tryPtr = 0;

        tries[tryTop][ROW] = r;

        tries[tryTop++][COL] = 0;

        while ((tryPtr < tryTop) && (!redWins))

        { r1 = tries[tryPtr][ROW];

          c1 = tries[tryPtr][COL];

          visited[r1][c1] = true;

          if (c1 == MAXCOLS - 1)

            redWins = true;

          else

          { if ((r1 - 1) >= 0)  /* check up */

            { if ((!visited[r1-1][c1]) && (board[r1-1][c1] == REDTOWER))

              { tries[tryTop][ROW] = r1-1;

                tries[tryTop++][COL] = c1;

            } }

            if ((r1 + 1) < MAXROWS)  /* check down */

            { if ((!visited[r1+1][c1]) && (board[r1+1][c1] == REDTOWER))

              { tries[tryTop][ROW] = r1+1;

                tries[tryTop++][COL] = c1;

            } }

            if ((c1 - 1) >= 0)  /* check left */

            { if ((!visited[r1][c1-1]) && (board[r1][c1-1] == REDTOWER))

              { tries[tryTop][ROW] = r1;

                tries[tryTop++][COL] = c1-1;

            } }

            /* check right */

            if ((c1 + 1) < MAXCOLS)  

            { if ((!visited[r1][c1+1]) && (board[r1][c1+1] == REDTOWER))

              { tries[tryTop][ROW] = r1;

                tries[tryTop++][COL] = c1+1;

          } } }

          tryPtr++;

        }

      }

    }

    if (redWins)

    { turnMsg.setText("Red Wins");

      if (debug)

        statusMsg.setText("Red Wins" + " MS: " + maxSteps + " MO: " + maxOptions + " MP: " + maxPathList + " MM: " + maxMoves);

  } }



  public static void setupMem()

  { int i;



    steps = new Step[MAXSTEPS];

    for (i = 0; i < MAXSTEPS; i++)

      steps[i] = new Step();



    optionList = new Option[MAXOPTIONS];

    for (i = 0; i < MAXOPTIONS; i++)

      optionList[i] = new Option();



    bluePathList = new PathList[MAXPATHLIST];

    for (i = 0; i < MAXPATHLIST; i++)

      bluePathList[i] = new PathList();



    redPathList = new PathList[MAXPATHLIST];

    for (i = 0; i < MAXPATHLIST; i++)

      redPathList[i] = new PathList();

  }



  public static void findBestMove()

  { int i, r, c, pth, stp, s, curStep, row, col;

    Point bestMove;



    stepCounter = 0;

    for (i = 0; i < MAXSTEPS; i++)

      steps[i].nextStep = i + 1;

    steps[MAXSTEPS-1].nextStep = -1;

    firstFreeStep = 0;



    visited = new boolean[MAXROWS][MAXCOLS];

    minSteps = new int[MAXROWS][MAXCOLS];

    consider = new boolean[MAXROWS][MAXCOLS];

    for (r = 0; r < MAXROWS; r++)

    { for (c = 0; c < MAXCOLS; c++)

      { visited[r][c] = false;

        minSteps[r][c] = MAXROWS * MAXCOLS;

        if ((r == 0) || (r == MAXROWS-1) || (c == 0) || (c == MAXCOLS-1))

          consider[r][c] = false;

        else

          consider[r][c] = true;

      }

    }



    optionTop = 0;

    bluePathListTop = 0;

    findShortestBluePaths();



    for (r = 0; r < MAXROWS; r++)

    { for (c = 0; c < MAXCOLS; c++)

      { visited[r][c] = false;

        minSteps[r][c] = MAXROWS * MAXCOLS;

        if ((r == 0) || (r == MAXROWS-1) || (c == 0) || (c == MAXCOLS-1))

          consider[r][c] = false;

        else

          consider[r][c] = true;

      }

    }

    optionTop = 0;

    redPathListTop = 0;

    findShortestRedPaths();

    if (debug)

      statusMsg.setText("BPLT: " + bluePathListTop + " RPLT: " + redPathListTop + " SC: " + stepCounter + " MS: " + maxSteps);

    bestMove = compareBlueAndRedLists();

    row = bestMove.y;

    col = bestMove.x;

    toggleBox(row,col);

    cnv1.repaint();

  }



  public static final int COUNT = 2, CLOSEST = 3;

  public static final int MAXDIST = MAXROWS * MAXCOLS;



  public static Point compareBlueAndRedLists()

  { int blueList[][], redList[][], tempBoard[][][], moveList[][];

    int blueTop, redTop, cmp, b, r, c, p, row, col, cp, lp, i, j;

    int close, closeCnt, lo, hi, mid, maxCount, count, moveListTop;



    boolean found, secureTop, secureBottom;

    Point rv;



    rv = new Point(0,0);



    secureTop = false;

    secureBottom = false;

    for (c = 1; c < MAXCOLS; c+=2)

    {  if (board[1][c] == BLUETOWER)

        secureTop = true;

      if (board[MAXROWS-2][c] == BLUETOWER)

        secureBottom = true;

    }

    if ((!secureTop) || (!secureBottom))

    { if (!secureTop)

      { for (b = 0; (b <= 6) && (!secureTop); b += 2)

        { for (c = 7-b; c <= 9+b; c += 2)

          { if (board[1][c] == NOTOWER)

            { rv.x = c;

              rv.y = 1;

              secureTop = true;

      } } } }

      else

      { for (b = 0; (b <= 6) && (!secureBottom); b += 2)

        { for (c = 7-b; c <= 9+b; c += 2)

          { if (board[MAXROWS-2][c] == NOTOWER)

            { rv.x = c;

              rv.y = MAXROWS-2;

              secureBottom = true;

    } } } } }

    else

    { 

      if ((redPathList[0].togo == 1) && (bluePathList[0].togo > 1))

      { /* Red has only one togo, must block it */

        cp = redPathList[0].firstStep;

        rv.x = -1;

        while ((cp != -1) && (rv.x == -1))

        { row = steps[cp].row;

          col = steps[cp].col;

          if (board[row][col] == NOTOWER)

          { rv.x = col;

            rv.y = row;

          }

          cp = steps[cp].nextStep;

        }

      }

      else

      { blueList = new int[MAXROWS*MAXCOLS][3];

        redList = new int[MAXROWS*MAXCOLS][4];

        tempBoard = new int[MAXROWS][MAXCOLS][2];  /* 0 = COUNT 1 = CLOSEST */

        moveList = new int[MAXROWS*MAXCOLS][2];

  

        for (r = 0; r < MAXROWS; r++)

        { for (c = 0; c < MAXCOLS; c++)

          { tempBoard[r][c][0] = 0;

            tempBoard[r][c][1] = 0;

        } }

  

        for (p = 0; p < bluePathListTop; p++)

        { cp = bluePathList[p].firstStep;

          while (cp != -1)

          { row = steps[cp].row;

            col = steps[cp].col;

            if (board[row][col] == NOTOWER)

            { tempBoard[row][col][0] += 1;

            }

            cp = steps[cp].nextStep;

        } }



        blueTop = 0;

        for (r = 0; r < MAXROWS; r++)

        { for (c = 0; c < MAXCOLS; c++)

          { if (tempBoard[r][c][0] != 0)

            { blueList[blueTop][ROW] = r;

              blueList[blueTop][COL] = c;

              blueList[blueTop++][COUNT] = tempBoard[r][c][0];

        } } }



        for (r = 0; r < MAXROWS; r++)

        { for (c = 0; c < MAXCOLS; c++)

          { tempBoard[r][c][0] = 0;

            tempBoard[r][c][1] = MAXDIST;

        } }

  

        lp = -1;

        for (p = 0; p < redPathListTop; p++)

        { cp = redPathList[p].firstStep;

          steps[cp].prevStep = -1;    /* This should have been taken care of elsewhere */

          closeCnt = MAXDIST;

          while (cp != -1)

          { row = steps[cp].row;

            col = steps[cp].col;

            if (board[row][col] == NOTOWER)

            { tempBoard[row][col][0] += 1;

              tempBoard[row][col][1] = Math.min(tempBoard[row][col][1], closeCnt++);

            }

            else

              closeCnt = 1;

            lp = cp;

            cp = steps[cp].nextStep;

          }

          closeCnt = MAXDIST;

          while (lp != -1)

          { row = steps[lp].row;

            col = steps[lp].col;

            if (board[row][col] == NOTOWER)

            { tempBoard[row][col][0] += 1;

              tempBoard[row][col][1] = Math.min(tempBoard[row][col][1], closeCnt++);

            }

            else

              closeCnt = 1;

            lp = steps[lp].prevStep;

          }

        }

  

        redTop = 0;

        for (r = 0; r < MAXROWS; r++)

        { for (c = 0; c < MAXCOLS; c++)

          { if (tempBoard[r][c][0] != 0)

            { redList[redTop][ROW] = r;

              redList[redTop][COL] = c;

              redList[redTop][COUNT] = tempBoard[r][c][0] / 2;

              redList[redTop++][CLOSEST] = tempBoard[r][c][1];

        } } }

  

  

        for (i = 0; i < blueTop-1; i++)

        { for (j = i; j < blueTop; j++)

          { cmp = compareRowCol(blueList[i][ROW], blueList[i][COL], blueList[j][ROW], blueList[j][COL]); 

            if (cmp == 1)

            { row = blueList[j][ROW];

              col = blueList[j][COL];

              count = blueList[j][COUNT];

              blueList[j][ROW] = blueList[i][ROW];

              blueList[j][COL] = blueList[i][COL];

              blueList[j][COUNT] = blueList[i][COUNT];

              blueList[i][ROW] = row;

              blueList[i][COL] = col;

              blueList[i][COUNT] = count;

        } } }

  

        for (i = 0; i < redTop-1; i++)

        { for (j = i; j < redTop; j++)

          { cmp = compareCloseRowCol(redList[i][CLOSEST], redList[i][ROW], redList[i][COL], redList[j][CLOSEST], redList[j][ROW], redList[j][COL]); 

            if (cmp == 1)

            { row = redList[j][ROW];

              col = redList[j][COL];

              count = redList[j][COUNT];

              close = redList[j][CLOSEST];

              redList[j][ROW] = redList[i][ROW];

              redList[j][COL] = redList[i][COL];

              redList[j][COUNT] = redList[i][COUNT];

              redList[j][CLOSEST] = redList[i][CLOSEST];

              redList[i][ROW] = row;

              redList[i][COL] = col;

              redList[i][COUNT] = count;

              redList[i][CLOSEST] = close;

        } } }



        r = 0;

        b = 0;

        found = false;

        rv.x = -1;

        maxCount = 0;

        close = MAXDIST;

        moveListTop = 0;

        while ((r < redTop) && (!found))

        { /* binsearch bluelist for redList[r][ROW]{COL] */

          lo = 0;

          hi = blueTop - 1;

          mid = 0;

          while ((lo <= hi) && (!found))

          { mid = (lo + hi) / 2;

            cmp = compareRowCol(redList[r][ROW], redList[r][COL], blueList[mid][ROW], blueList[mid][COL]);

            if (cmp > 0)

              lo = mid + 1;

            else

              if (cmp == 0)

                found = true;

              else

                hi = mid - 1;

          }

          if (found)

          { /* All those in moveList will have same Count and Closeness */

            if ( (blueList[mid][COUNT] + redList[mid][COUNT] >= maxCount)

               && (redList[r][CLOSEST] <= close))

            { if ( (blueList[mid][COUNT] + redList[mid][COUNT] > maxCount)

               || (redList[r][CLOSEST] < close))

                moveListTop = 0;

              moveList[moveListTop][ROW] = blueList[mid][ROW];

              moveList[moveListTop++][COL] = blueList[mid][COL];

              maxCount = blueList[mid][COUNT];

              close = redList[r][CLOSEST];

            }

            found = false;

          }

          r++;

        }

        if (moveListTop == 0)

        { for (b = 0; b < blueTop; b++)

          { if (blueList[b][COUNT] >= maxCount)

            { if (blueList[b][COUNT] > maxCount)

                moveListTop = 0;

              moveList[moveListTop][ROW] = blueList[b][ROW];

              moveList[moveListTop++][COL] = blueList[b][COL];

              maxCount = blueList[b][COUNT];

        } } }

        maxMoves = Math.max(moveListTop, maxMoves);

        b = (int) (Math.random() * moveListTop);

        rv.x = moveList[b][COL];

        rv.y = moveList[b][ROW];

    } }

    return(rv);

  }



  /* Returns -1 if row1,col1 < row2, col2 0 if equal +1 if greater */

  public static int compareCloseRowCol(int close1, int row1, int col1, int close2, int row2, int col2)

  { int rc1, rc2;



    rc1 = (close1 * 2000) + (row1 * 50) + col1;

    rc2 = (close2 * 2000) + (row2 * 50) + col2;

    if (rc1 == rc2)

      return(0);

    else

      if (rc1 < rc2)

        return(-1);

      else

        return(+1);



  }

  /* Returns -1 if row1,col1 < row2, col2 0 if equal +1 if greater */

  public static int compareRowCol(int row1, int col1, int row2, int col2)

  { int rc1, rc2;



    rc1 = (row1 * 100) + col1;

    rc2 = (row2 * 100) + col2;

    if (rc1 == rc2)

      return(0);

    else

      if (rc1 < rc2)

        return(-1);

      else

        return(+1);



  }



  public static int newStep()

  { int rv;

    rv = firstFreeStep;

    stepCounter++;

    maxSteps = Math.max(stepCounter, maxSteps);

    firstFreeStep = steps[firstFreeStep].nextStep;

    if (firstFreeStep == -1)

    { if (debug)

      { statusMsg.setText("Out of Memory for Steps.");

        System.out.println("StepCounter: " + stepCounter);

      }

      else

        turnMsg.setText("Out of Memory for Steps.");

    }

    steps[rv].nextStep = -1;

    return(rv);

  }



  public static void deleteStep(int stepNum)

  {

    stepCounter--;

    steps[stepNum].nextStep = firstFreeStep;

    firstFreeStep = stepNum;

  }

  

  public static void findShortestBluePaths()

  { int pathHead, pathHeadLength, pathHeadTogo, minTogo, c, row, col;

    int stepCnt, prevStep, nextStep, curStep, lastStep, targ, cp, lp;

    int row1, col1, ph, pathCnt, c1;



    minTogo = MAXROWS * MAXCOLS;



    pathCnt = 0;

    for (c = 1; c < MAXCOLS - 1; c+=2)

    { // System.out.println("Column: " + c);

      /* No need to consider row1 except for column c */

      for (c1 = 1; c1 < MAXCOLS - 1; c1+= 2)

      { if (c1 != c)

          consider[1][c1] = false;

        else

          consider[1][c1] = true;

      }

      if (board[1][c] != REDTOWER)

      { curStep = newStep();

        pathHead = curStep;

        steps[curStep].row = 1;

        steps[curStep].col = c;

        steps[curStep].stepCnt = 1;

        steps[curStep].direction = DOWN;

        steps[curStep].nextStep = -1;

        steps[curStep].prevStep = -1;

        pathHeadLength = 1;

        if (board[1][c] == NOTOWER)

          pathHeadTogo = 1;

        else

          pathHeadTogo = 0;

        visited[1][c] = true;

        optionTop = 0;

        row1 = 2;

        col1 = c;

        stepCnt = 2;

        /* check right */

        considerBlueMove(stepCnt, row1, col1+1, RIGHT);



        /* check LEFT */

        considerBlueMove(stepCnt, row1, col1-1, LEFT);



        /* check DOWN */

        considerBlueMove(stepCnt, row1+1, col1, DOWN);



        lastStep = curStep;

        stepCnt = 3;

        while (optionTop > 0)

        { optionTop--;

          /* makeMove(optionList[optionTop]); */

          while (optionList[optionTop].stepCnt <= steps[lastStep].stepCnt)

          { row = steps[lastStep].row;

            col = steps[lastStep].col;

            visited[row][col] = false;

            pathHeadLength--;

            if (board[row][col] != BLUETOWER)

              pathHeadTogo--;

            lastStep = steps[lastStep].prevStep;

            deleteStep(steps[lastStep].nextStep);

            steps[lastStep].nextStep = -1;

          }

          curStep = newStep();

          steps[lastStep].nextStep = curStep;

          steps[curStep].prevStep = lastStep;

          steps[curStep].row = optionList[optionTop].row;

          steps[curStep].col = optionList[optionTop].col;

          steps[curStep].stepCnt = optionList[optionTop].stepCnt;

          steps[curStep].direction = optionList[optionTop].direction;

          steps[curStep].nextStep = -1;

          pathHeadLength++;

          row = steps[curStep].row;

          col = steps[curStep].col;

          if (board[row][col] == NOTOWER)

            pathHeadTogo++;

          visited[row][col] = true;



          if ((steps[curStep].row == MAXROWS - 2)

           || (pathHeadTogo > minTogo)

           || (pathHeadTogo > minSteps[row][col]))

          { if ( (steps[curStep].row == MAXROWS - 2) 

              && (pathHeadTogo <= minTogo))

            { /* savePath(); */

              if (pathHeadTogo < minTogo) /* replace current shortest path(s) */

              { deleteBluePathList();

                targ = 0;

                bluePathListTop = 1;

                minTogo = pathHeadTogo;

              }

              else  /* path HeadTogo = minTogo */

              { if (bluePathListTop < MAXPATHLIST)  /* add to list of shortest path(s) */

                { targ = bluePathListTop++;

                  maxPathList = Math.max(bluePathListTop, maxPathList);

                }

                else

                  targ = MAXPATHLIST;

              }

              if (targ == MAXPATHLIST)

              { if (debug)

                  statusMsg.setText("Out of space for Blue PathList");

                else

                  turnMsg.setText("");

              }

              else

              { cp = newStep();

                bluePathList[targ].length = pathHeadLength;

                bluePathList[targ].togo = pathHeadTogo;

                bluePathList[targ].firstStep = cp;

                steps[cp].row = steps[pathHead].row;

                steps[cp].col = steps[pathHead].col;

                steps[cp].stepCnt = steps[pathHead].stepCnt;

                steps[cp].direction = steps[pathHead].direction;

                ph = steps[pathHead].nextStep;

                lp = cp;

                while (ph != -1)

                { cp = newStep();

                  steps[lp].nextStep = cp;

                  steps[cp].prevStep = lp;

                  steps[cp].row = steps[ph].row;

                  steps[cp].col = steps[ph].col;

                  steps[cp].stepCnt = steps[ph].stepCnt;

                  steps[cp].direction = steps[ph].direction;

                  ph = steps[ph].nextStep;

                  lp = cp;

                }

                steps[lp].nextStep = -1;

                /* Be sure pointers are left in right state for recursion */

            } }

/*          else   bailout */

          }

          else  /* keep going */

          { minSteps[row][col] = pathHeadTogo;

            switch (steps[curStep].direction)   /* ROW1, COL1 is location of initial BLUETOWER */

            { case UP:

                row1 = steps[curStep].row - 1;

                col1 = steps[curStep].col;

                break;

              case DOWN:

                row1 = steps[curStep].row + 1;

                col1 = steps[curStep].col;

                break;

              case LEFT:

                row1 = steps[curStep].row;

                col1 = steps[curStep].col-1;

                break;

              case RIGHT:

                row1 = steps[curStep].row;

                col1 = steps[curStep].col+1;

                break;

            }



            stepCnt = steps[curStep].stepCnt + 1;

            /* check UP */

            considerBlueMove(stepCnt, row1-1, col1, UP);



            /* check right */

            considerBlueMove(stepCnt, row1, col1+1, RIGHT);



            /* check LEFT */

            considerBlueMove(stepCnt, row1, col1-1, LEFT);



            /* check DOWN */

            considerBlueMove(stepCnt, row1+1, col1, DOWN);

          }

          lastStep = curStep;

        } /* End While (optionTop > 0) */

        while (lastStep != -1)

        { row = steps[lastStep].row;

          col = steps[lastStep].col;

          visited[row][col] = false;

          lp = steps[lastStep].prevStep;

          deleteStep(lastStep);

          lastStep = lp;

        }

      }   /* end if board[1][c] != REDTOWER */

    } /* End for c = 1 to MAXCOLS */

  }



  public static void deleteBluePathList()

  { int p, lp, cp;



    for (p = 0; p < bluePathListTop; p++)

    { cp = bluePathList[p].firstStep;

      while (cp != -1)

      { lp = cp;

        cp = steps[cp].nextStep;

        deleteStep(lp);

      }

    }

    bluePathListTop = 0;

  }



  public static void considerBlueMove(int stepCnt, int row2, int col2, int direction)

  {

    if ((consider[row2][col2])

     && (!visited[row2][col2])

     && (board[row2][col2] != REDTOWER) )

    { optionList[optionTop].stepCnt = stepCnt;

      optionList[optionTop].row = row2;

      optionList[optionTop].col = col2;

      optionList[optionTop].direction = direction;

      optionTop++;

      maxOptions = Math.max(optionTop, maxOptions);

    }

  }



  public static void findShortestRedPaths()

  { int pathHead, pathHeadLength, pathHeadTogo, minTogo, row, col;

    int stepCnt, prevStep, nextStep, curStep, lastStep, targ, cp, lp;

    int row1, col1, ph, pathCnt, r, r1;



    minTogo = MAXROWS * MAXCOLS;



    pathCnt = 0;

    for (r = 1; r < MAXROWS - 1; r+=2)

    { // System.out.println("Row: " + r);

      /* No need to consider col1 except for row r */

      for (r1 = 1; r1 < MAXROWS - 1; r1+= 2)

      { if (r1 != r)

          consider[r1][1] = false;

        else

          consider[r1][1] = true;

      }

      if (board[r][1] != BLUETOWER)

      { curStep = newStep();

        pathHead = curStep;

        steps[curStep].row = r;

        steps[curStep].col = 1;

        steps[curStep].stepCnt = 1;

        steps[curStep].direction = RIGHT;

        steps[curStep].nextStep = -1;

        steps[curStep].prevStep = -1;

        pathHeadLength = 1;

        if (board[r][1] == NOTOWER)

          pathHeadTogo = 1;

        else

          pathHeadTogo = 0;

        visited[r][1] = true;

        optionTop = 0;

        row1 = r;

        col1 = 2;

        stepCnt = 2;



        /* check UP */

        considerRedMove(stepCnt, row1-1, col1, UP);



        /* check DOWN */

        considerRedMove(stepCnt, row1+1, col1, DOWN);



        /* check right */

        considerRedMove(stepCnt, row1, col1+1, RIGHT);



        lastStep = curStep;

        stepCnt = 3;

        while (optionTop > 0)

        { optionTop--;

          /* makeMove(optionList[optionTop]); */

          while (optionList[optionTop].stepCnt <= steps[lastStep].stepCnt)

          { row = steps[lastStep].row;

            col = steps[lastStep].col;

            visited[row][col] = false;

            pathHeadLength--;

            if (board[row][col] != REDTOWER)

              pathHeadTogo--;

            lastStep = steps[lastStep].prevStep;

            deleteStep(steps[lastStep].nextStep);

            steps[lastStep].nextStep = -1;

          }

          curStep = newStep();

          steps[lastStep].nextStep = curStep;

          steps[curStep].prevStep = lastStep;

          steps[curStep].row = optionList[optionTop].row;

          steps[curStep].col = optionList[optionTop].col;

          steps[curStep].stepCnt = optionList[optionTop].stepCnt;

          steps[curStep].direction = optionList[optionTop].direction;

          steps[curStep].nextStep = -1;

          pathHeadLength++;

          row = steps[curStep].row;

          col = steps[curStep].col;

          if (board[row][col] == NOTOWER)

            pathHeadTogo++;

          visited[row][col] = true;



          if ((steps[curStep].col == MAXCOLS - 2)

           || (pathHeadTogo > minTogo)

           || (pathHeadTogo > minSteps[row][col]))

          { if ( (steps[curStep].col == MAXCOLS - 2) 

              && (pathHeadTogo <= minTogo))

            { /* savePath(); */

              if (pathHeadTogo < minTogo) /* replace current shortest path(s) */

              { deleteRedPathList();

                targ = 0;

                redPathListTop = 1;

                minTogo = pathHeadTogo;

              }

              else  /* path HeadTogo = minTogo */

              { if (redPathListTop < MAXPATHLIST)  /* add to list of shortest path(s) */

                { targ = redPathListTop++;

                  maxPathList = Math.max(redPathListTop, maxPathList);

                }

                else

                  targ = MAXPATHLIST;

              }

              if (targ == MAXPATHLIST)

              { if (debug)

                  statusMsg.setText("Out of space for Red PathList");

                else

                  turnMsg.setText("");

              }

              else

              { cp = newStep();

                redPathList[targ].length = pathHeadLength;

                redPathList[targ].togo = pathHeadTogo;

                redPathList[targ].firstStep = cp;

                steps[cp].row = steps[pathHead].row;

                steps[cp].col = steps[pathHead].col;

                steps[cp].stepCnt = steps[pathHead].stepCnt;

                steps[cp].direction = steps[pathHead].direction;

                ph = steps[pathHead].nextStep;

                lp = cp;

                while (ph != -1)

                { cp = newStep();

                  steps[lp].nextStep = cp;

                  steps[cp].prevStep = lp;

                  steps[cp].row = steps[ph].row;

                  steps[cp].col = steps[ph].col;

                  steps[cp].stepCnt = steps[ph].stepCnt;

                  steps[cp].direction = steps[ph].direction;

                  ph = steps[ph].nextStep;

                  lp = cp;

                }

                steps[lp].nextStep = -1;

                /* Be sure pointers are left in right state for recursion */

            } }

/*          else   bailout */

          }

          else  /* keep going */

          { minSteps[row][col] = pathHeadTogo;

            switch (steps[curStep].direction)   /* ROW1, COL1 is location of initial RedTOWER */

            { case UP:

                row1 = steps[curStep].row - 1;

                col1 = steps[curStep].col;

                break;

              case DOWN:

                row1 = steps[curStep].row + 1;

                col1 = steps[curStep].col;

                break;

              case LEFT:

                row1 = steps[curStep].row;

                col1 = steps[curStep].col-1;

                break;

              case RIGHT:

                row1 = steps[curStep].row;

                col1 = steps[curStep].col+1;

                break;

            }



            stepCnt = steps[curStep].stepCnt + 1;

            /* check LEFT */

            considerRedMove(stepCnt, row1, col1-1, LEFT);



            /* check UP */

            considerRedMove(stepCnt, row1-1, col1, UP);



            /* check DOWN */

            considerRedMove(stepCnt, row1+1, col1, DOWN);



            /* check right */

            considerRedMove(stepCnt, row1, col1+1, RIGHT);

          }

          lastStep = curStep;

//          if (pathCnt++ < 20)

//            displayPath(pathHead, pathHeadLength, pathHeadTogo);

        } /* End While (optionTop > 0) */

        while (lastStep != -1)

        { row = steps[lastStep].row;

          col = steps[lastStep].col;

          visited[row][col] = false;

          lp = steps[lastStep].prevStep;

          deleteStep(lastStep);

          lastStep = lp;

        }

      }   /* end if board[1][c] != BLUETOWER */

    } /* End for r = 1 to MAXROWS */

  }



  public static void deleteRedPathList()

  { int p, lp, cp;



    for (p = 0; p < redPathListTop; p++)

    { cp = redPathList[p].firstStep;

      while (cp != -1)

      { lp = cp;

        cp = steps[cp].nextStep;

        deleteStep(lp);

      }

    }

    redPathListTop = 0;

  }



  public static void considerRedMove(int stepCnt, int row2, int col2, int direction)

  {

    if ((consider[row2][col2])

     && (!visited[row2][col2])

     && (board[row2][col2] != BLUETOWER) )

    { optionList[optionTop].stepCnt = stepCnt;

      optionList[optionTop].row = row2;

      optionList[optionTop].col = col2;

      optionList[optionTop].direction = direction;

      optionTop++;

      maxOptions = Math.max(optionTop, maxOptions);

    }

  }



//  public static void main(String args[]) {

//    Bridges bridgeApp = null;

//    bridgeApp = new Bridges("Bridge Application");

//    bridgeApp.resize(MAXSCREENX, MAXSCREENY+75);

//    bridgeApp.show(true);

//  }



}