algorithm - 在我的递归方法中继续越界以导航并查找 4X4 矩阵中的所有字母组合

Question

这是 Boggle 求解器的一部分。 我做了一个递归方法来遍历字符串矩阵。 MyLetteres 存储了所有字符(例如 a、b、c...)，MyLetteres1 初始化为空，tracker 用于错误。这些变量标记了我已经访问过的矩阵中的哪些坐标(我无法重新访问坐标)。我只能移动到相邻的坐标(不能跳过)。参数 String word 用单个字母(起点)初始化。 int x 和 int y 是我的 (x,y) 坐标。忽略 int p 和 int n。

我遇到的问题是我似乎无法正确标记该方法已经过的坐标，然后我似乎无法将 tracker (最后一行)重置为 false 下一个要运行的 getPaths()。

这是我的代码，请帮忙!

public void getPaths(int p, int n,int x, int y,String word, boolean tracker[][],boolean MyLetteres1[][],String MyLetteres[][],boolean checker)throws IOException{
    if(word.length()>1)
        checker=Check(word);//Check() just checks to see if its a word.
    tracker[x][y]=true;//makes sure that the checkers never goes back over starting letter
    if(x+1<MyLetteres.length&&tracker[x+1][y]==false){//up{
        //checker=Check(word);//checks to see if its word 
        //reverse(word);
        System.out.print("1 ("+x+","+y+"), ");//for debugging purposes
        getPaths(n,p,x+1, y,word+MyLetteres[x+1][y], tracker,MyLetteres1,MyLetteres,true);//recursive part
    }
    if(x-1>0&&tracker[x-1][y]==false){//down
        //checker=Check(word);
        //reverse(word);
        System.out.print("2 ("+x+","+y+"), ");
        getPaths(n,p,x-1, y ,word+MyLetteres[x-1][y], tracker,MyLetteres1,MyLetteres,true);
    }
    if(y+1<MyLetteres.length&&tracker[x][y+1]==false){//right
        //checker=Check(word);
        //reverse(word);
        System.out.print("3 ("+x+","+y+"), ");
        getPaths(n, p,x , y+1,word+MyLetteres[x][y+1], tracker,MyLetteres1,MyLetteres,true);
    }
    if(y-1>0&&tracker[x][y-1]==false){//left
        //checker=Check(word);
        //reverse(word);
        System.out.print("4 ("+x+","+y+"), ");
        getPaths(n,p,x , y-1,word+MyLetteres[x][y-1], tracker,MyLetteres1,MyLetteres,true);
    }
    if(x+1<MyLetteres.length&&y+1<MyLetteres.length&&tracker[x+1][y+1]==false){//right, up
        //checker=Check(word);
        //reverse(word);
        System.out.print("5 ("+x+","+y+"), ");
        getPaths(n,p,x+1, y+1,word+MyLetteres[x+1][y+1], tracker,MyLetteres1,MyLetteres,true);
    }
    if(x-1>0&&y-1>0&&tracker[x-1][y-1]==false){//down, left
        //checker=Check(word);
        //reverse(word);
        System.out.print("6 ("+x+","+y+"), ");
        getPaths(n,p,x-1, y-1,word+MyLetteres[x-1][y-1], tracker,MyLetteres1,MyLetteres,true);
    }
    if(x-1>0&&y+1<MyLetteres.length&&tracker[x-1][y+1]==false){//down, right
        //checker=Check(word);
        //reverse(word);
        System.out.print("7 ("+x+","+y+"), ");
        getPaths(n,p,x+1, y-1, word+MyLetteres[x-1][y+1],tracker,MyLetteres1,MyLetteres,true);
    }
    if(x+1<MyLetteres.length&&y-1>0&&tracker[x+1][y-1]==false){//up, left
        //checker=Check(word);
        //reverse(word);
        System.out.print("8 ("+x+","+y+"), ");
        getPaths(n, p,x-1 , y+1, word+MyLetteres[x+1][y-1],tracker,MyLetteres1,MyLetteres,true);
    }
    tracker=deepCopyBoolean(MyLetteres1);//MyLetteres1 never changes so this is my attempt at resetting tracker (which does change) back to all false so that when the program starts a new path, nothing has been "visited".
 }

Answer 1

您可以做很多事情来帮助我们或您自己解决这个问题。最重要的是，如果你要出界，你应该知道它发生在哪条线上。您的调试器可以告诉您这一点，并且告诉我们这将大有帮助。 它也有助于告诉我们您正在使用哪种语言进行编码。对我来说它看起来像 Java。

在这种情况下，它看起来像你的最后两个 if语句，你传递了错误的 x和 y getPaths 中的值。你有

if(x-1>0&&y+1 ... getPaths(n,p,x+1,y-1

和

if(x+1<MyLetteres.length&&y-1>0 ... getPaths(n, p, x-1, y+1

修复这些问题，您可能会修复超出范围的异常。

顺便说一句，当您检查您的范围时，您可能想要检查 x >= 0和 y >= 0而不是 x > 0和 y > 0 .数组索引等于 0 是有效的。

此外，检查 x + 1 < MyLetteres.length 是否在技术上是不准确的如果y + 1 < MyLetteres.length ，因为那是说“x + 1 小于板的'高度'”和“y + 1 小于板的'高度'”。因为你的板子是正方形的，所以效果不错，但准确地说，你应该有 x + 1 < MyLetteres[0].length ，这就是说“x + 1 小于板的‘宽度’。

最后，关于重置跟踪器，我建议允许它为 null，并在顶级调用中将其作为 null 传递。如果它为 null，则您知道您正处于一个新单词的开头，您可以创建自己的单词并将其传递到所有后续的递归调用中。

祝你好运!