java - 使用递归计算 Matrix Java 中连接字符串的数量

Question

我应该计算有多少个@符号连接到二维数组矩阵中的原始预定点。我收到堆栈溢出错误，但不知道为什么。欢迎任何建议(获取提供的行和列位置，并计算有多少 @ 符号连接到原始位置。如果 @ 符号向上、向下、向左和向右相互连接，则它们是连接的。)

当前代码:

   import static java.lang.System.*;

public class AtCounter
{
   private String[][] atMat;
   private int totalCount = 0;
   private boolean[][] visited; //used to see if location has been visited before.
   public AtCounter(int rows, int cols)
   {
       //size the matrix
       atMat = new String[rows][cols];
       //use nested loops to randomly load the matrix
       for(int r = 0; r < atMat.length; r++)
       {
           for(int c = 0; c < atMat[r].length; c++)
           {
               int num = (int) (Math.random() * 2);
               if(num == 0)
                   atMat[r][c] = "@";
               else
                   atMat[r][c] = "-";
           }
       }
       //you will need to use Math.random()

        visited = new boolean[atMat.length][atMat.length];
   }
   /**
    * Used to find out if location is in the 2D Matrix.
    */
   public boolean inBounds(int r, int c)
   {
        return ((r > -1 && r < atMat.length) && (c > -1 && c < atMat.length));
   }
   public int countAts(int r, int c)
   {
        //add in recursive code to count up the # of @s connected
        //start checking at spot [r,c]

        if(atMat[r][c].equals("-") || !inBounds(r,c))
            return 0;
        if(!visited[r][c])
        {
            if(atMat[r][c].equals("@"))
            {
                totalCount+=1;

                if(inBounds(r - 1, c))//up
                    countAts(r - 1, c);

                if(inBounds(r + 1, c))//down
                    countAts(r + 1, c);

                if(inBounds(r, c + 1))//right
                    countAts(r , c + 1);

                if(inBounds(r, c  - 1))//left
                    countAts(r, c - 1);
            }
        }
        return totalCount;        
     }


    /*
     *this method will return all values in the matrix
     *this method should return a view of the matrix
     *that looks like a matrix
     */
    public String toString()
    {
        String grid = "";
        for(String[] row : atMat)
        {
            for(String val : row)
            {
                grid += val + " ";
            }
            grid += "\n";
        }
        return grid;
    }
}

Answer 1

您的代码中有几个错误:

• 您使用atMat.length创建了visited数组，即使您的原始尺寸(行和>cols) 不相等。
• 在 inBounds 方法中，列参数 c 对应的是行的长度，而不是列的长度
• 在 countAts 方法中:
  • 无效条件的检查顺序需要颠倒，您需要先检查该位置是否有效，然后再检查该单元格中的值是否为@。
  • 如果当前单元格尚未被访问过，那么首先要在 if block 中将其标记为已访问，以避免陷入无限递归。

综上所述，可能的解决方案如下:

import static java.lang.System.*;

public class AtCounter
{
    private String[][] atMat;
    private int totalCount = 0;
    private boolean[][] visited; //used to see if location has been visited before.

    private int rows; // To store rows length
    private int cols; // To store cols length

    public AtCounter(int rows, int cols)
    {
        //size of the matrix
        this.rows = rows;
        this.cols = cols;
        atMat = new String[rows][cols];

        //use nested loops to randomly load the matrix
        for(int r = 0; r < rows; r++)
            for(int c = 0; c < cols; c++) {
                int num = (int) (Math.random() * 2);
                if(num == 0)
                    atMat[r][c] = "@";
                else
                    atMat[r][c] = "-";
            }

        visited = new boolean[rows][cols];
    }

    /**
    * Used to find out if location is in the 2D Matrix.
    */
    public boolean inBounds(int r, int c)
    {
        return r > -1 && r < rows && c > -1 && c < cols;
    }

    public int countAts(int r, int c)
    {
        //add in recursive code to count up the # of @s connected
        //start checking at spot [r,c]

        if(!inBounds(r,c) || atMat[r][c].equals("-")) // The order here matters
            return 0;

        if(!visited[r][c])
        {
            visited[r][c] = true; // Marks the current cell as visited
            if(atMat[r][c].equals("@"))
            {
                totalCount+=1;

                if(inBounds(r - 1, c))//up
                    countAts(r - 1, c);

                if(inBounds(r + 1, c))//down
                    countAts(r + 1, c);

                if(inBounds(r, c + 1))//right
                    countAts(r , c + 1);

                if(inBounds(r, c  - 1))//left
                    countAts(r, c - 1);
            }
        }
        return totalCount;
    }

}