出现 java.lang.ArrayIndexOutOfBoundsException: -1 错误。递归填充

Question

我正在尝试制作一个填充游戏，将数字打印到控制台 window 并允许用户选择一个数字，以便 "fill" 具有相同数字的二维数组. objective 是用你的颜色填充二维数组。我使用 4 路递归方法来填充这些数字。任何时候我运行这个，并尝试输入一个 "color," 它抛出这个错误：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
     at Board.floodFill(Board.java:57)
     at Board.floodFill(Board.java:68)
     at Board.move(Board.java:47)
     at FloodIt.main(FloodIt.java:30)

这是我的代码：

class FloodIt {

    public static void main(String args[]) {
        Scanner scan=new Scanner(System.in);
        System.out.println("Welcome to the Flood-It Game.");
        System.out.println("*****************************");
        System.out.println("How large of a board would you like?");
        System.out.println("I would suggest sizes between 3x3 and 20x20.");
        System.out.println("And colors between 3 and 6.");
        String again="";
        do {
            System.out.print("Enter the one digit number of the board width (3-20): ");
            int size=Integer.parseInt(scan.nextLine());
            System.out.print("Enter the number of colors (3-6): ");
            int numColors=Integer.parseInt(scan.nextLine());
            Board board=new Board(size,numColors);
            while(!board.finished()) {
                System.out.print(board);
                System.out.print("What color do you choose? ");
                int color=Integer.parseInt(scan.nextLine());
                board.move(color);
            }
            System.out.println("Nice job, you finished in "+board.numMoves());
            System.out.print("Would you like to play again (Y/N)? ");
            again=scan.nextLine();
        } while (again.equalsIgnoreCase("Y"));
    }
}

import java.util.Random;

/**The board class for the Flood-It game.  This class implements a NxN board filled with numColors colors.
 * The class implements several methods to allow the playing of the game.
 */
class Board {
    private int moves;
    private int[][] board;//a 2D array
    Random rand = new Random();

    /**Constructs a new sizeXsize board filled where each element on the board is a random number between 0
     * and numcolors.  Also initializes the number of moves to zero.
     * @param size the size of the board
     * @param numColors the number of possible entries on the board
     */
    public Board(int size,int numColors) {
        moves=0;
        board = new int[size][size];
        for(int row=0;row<board.length;row++){
            for(int col = 0;col<board[row].length;col++){
                board[row][col]=rand.nextInt(numColors);
            }
        }
    }


    /**Updates the board to fill (from the top left corner) with a specificed color.  
     * Filling stops when any other color is hit besides the one in the top left corner.
     * Play the game at http://floodit.cs.bris.ac.uk/About.aspx to get a better understanding of what
     * this method should do.  You will probably also want to take a look at the algorithm described
     * at http://en.wikipedia.org/wiki/Flood_fill which describes what this method should do.
     * You are free to have this method call other methods (I would recommend creating a private method that
     * this method calls.).
     * @param color the new color to flood the board with.
     */

    public void move(int color) {
        floodFill(0,0,board[0][0],color);
        moves++;

    }

    private void floodFill(int row, int col, int origColor,int newColor){
        //base case
        if(origColor==newColor){
            return;
        }
        if(board[row][col]!=origColor){
            return;
        }
        if(row<0||col<0){
            //do nothing
            return;
        }


        board[row][col]=newColor;

        floodFill(row,col-1,origColor,newColor);
        floodFill(row,col+1,origColor,newColor);
        floodFill(row-1,col,origColor,newColor);
        floodFill(row+1,col,origColor,newColor);    
    }


    /**returns true if the board is not completely filled with a single color.
     * Otherwise it returns false.
     * @return true if board is all one color
     */
    public boolean finished() {
        //TODO finish this method

        return false;
    }


    /**returns how many times the move() method has been called.
     * @return the number of times the move() method has been called.
     */
    public int numMoves() {
        return moves;
    }


    /**Returns a string representation of the board.  Use tabs between elements of the board.
     * And have every row of the board be a seperated by a newline character.
     * Example:
     * "1\t0\t3\t\n2\t0\t2\t\n1\t0\t1\t\n"
     * @return a String representation of the board
     */
    public String toString() {
        String result = "";
        for(int row=0;row<board.length;row++){
            for(int col = 0;col<board[row].length;col++){
                result += board[row][col]+"\t";
            }
            result+="\n";
        }return result; 
    }
}

Answer 1

在您的 floodFill 方法中，您在调用 board[row][col]=newColor.

之前没有检查 row 或 col 是否在范围内

您的代码：

if(row<0||col<0){
        //do nothing
        return;
}

应该放在函数的较高位置，以便在 board[row][col]=newColor 之前检查它。它还需要检查它是否大于数组的宽度和高度。

正确代码：

if(row<0||col<0||row>=board.length||col>=board[0].length)
{
   return;
}

Answer 2

您检查

if(row<0||col<0)

所以 row 和 col 都可以是 0.

那么你有

    floodFill(row,col-1,origColor,newColor);
    floodFill(row,col+1,origColor,newColor);
    floodFill(row-1,col,origColor,newColor);
    floodFill(row+1,col,origColor,newColor);

所以两者中的任何一个都可能成为 -1。

您的代码具有以下验证序列：

   if(board[row][col]!=origColor){
        return;
    }
    if(row<0||col<0){
        //do nothing
        return;
    }

第一个if你可以有[-1]。如果你交换两个 if 就不可能了。

出现 java.lang.ArrayIndexOutOfBoundsException: -1 错误。递归填充

Having a java.lang.ArrayIndexOutOfBoundsException: -1 error. RECURSIVE FLOODFILL

java

recursion

flood-fill

indexoutofboundsexception