поэтому я относительно новичок в Java (в настоящее время я беру AP java в своей школе), и я пытаюсь разработать рекурсивный алгоритм для решения n * n board, и я чувствую, что очень близок, но еще не совсем там. У меня есть все, что написано, чтобы просмотреть мой словарь, чтобы определить, являются ли буквы, которые я отправляю, словами или нет, и т. д. Мой алгоритм состоит в том, чтобы начальная буква была (n, p) в моем массиве, отправить эти координаты другому методу, который будет идти во всех направлениях, чтобы найти все возможные комбинации. как только все комбинации, начинающиеся с (n, p), будут найдены, я буду увеличивать p до тех пор, пока он не дойдет до конца строки, затем я буду увеличивать n и снова начинать p с 0. (Я просматриваю только половину букв, потому что комбинации одинаковы в обоих направлениях)
Часть, с которой у меня проблемы, — это рекурсивная последовательность, потому что, когда я прохожу определенную позицию на доске, я хочу пометить ее, чтобы убедиться, что я никогда не пройду ее снова до конца последовательности. Это не работает полностью, и мне было интересно, может ли кто-нибудь сказать мне, почему/помогите мне написать лучший алгоритм. заранее спасибо
public void AllLetters(int n, int p, int x, int y,String word, String MyLetteres[][]){
int temp=0;
int StartLetter =(int)(Math.pow(MyLetteres.length,2));
while(temp<StartLetter)//runs through every letter
{
if(temp==0)
getPaths(p, n,x,y,word, MyLetteres);
else if(temp%(MyLetteres.length-1)==temp){
getPaths(p, n+1,x,y,word, MyLetteres);
}
else {
getPaths(p+1, 0,x,y,word, MyLetteres);
}
if(temp==(StartLetter/2-1)){
temp=StartLetter;
}
temp++;
}
}
public void getPaths(int p, int n, int x, int y,String word, String MyLetteres[][]){
if( x ==p-1 && y == n-1){//reach the (n,p) point
System.out.print("");
}else if( x >= MyLetteres.length || y >= MyLetteres.length||x < 0 || y < 0){//out of bounds
return;
}else {
if(x+1<MyLetteres.length&&!MyLetteres[x+1][y].equals("0")){//up{
word=word+""+MyLetteres[x+1][y];
Check(word);//function that checks if it is a word
reverse(word);//checks its a word backwards (for efficenicy)
MyLetteres[x+1][y]="0";//marking that I've used this position
System.out.print("1");//debugging purposes
getPaths(n,p, x +1, y,word , MyLetteres);
}
if(x-1>0&&!MyLetteres[x-1][y].equals("0")){//down
word=word+""+MyLetteres[x-1][y];
Check(word);
reverse(word);
MyLetteres[x-1][y]="0";
System.out.print("2");
getPaths(n,p, x -1, y ,word, MyLetteres);
}
if(y+1<MyLetteres.length&&!MyLetteres[x][y+1].equals("0")){//right
word=word+""+MyLetteres[x][y+1];
Check(word);
reverse(word);
MyLetteres[x][y+1]="0";
System.out.print("3");
getPaths(n, p,x , y +1,word, MyLetteres);
}
if(y-1>0&&!MyLetteres[x][y-1].equals("0")){//left
word=word+""+MyLetteres[x][y-1];
Check(word);
reverse(word);
MyLetteres[x][y-1]="0";
System.out.print("4");
getPaths(n,p, x , y -1,word, MyLetteres);
}
if(x+1<MyLetteres.length&&y+1<MyLetteres.length&&!MyLetteres[x+1][y+1].equals("0")){//right, up
word=word+""+MyLetteres[x+1][y+1];
Check(word);
reverse(word);
MyLetteres[x+1][y+1]="0";
System.out.print("5");
getPaths(n,p, x +1, y +1,word, MyLetteres);
}
if(x-1>0&&y-1>0&&!MyLetteres[x-1][y-1].equals("0")){//down, left
word=word+""+MyLetteres[x-1][y-1];
Check(word);
reverse(word);
MyLetteres[x-1][y-1]="0";
System.out.print("6");
getPaths(n,p, x-1 , y -1,word, MyLetteres);
}
if(x-1>0&&y+1<MyLetteres.length&&!MyLetteres[x-1][y+1].equals("0")){//down, right
word=word+""+MyLetteres[x-1][y+1];
Check(word);
reverse(word);
MyLetteres[x-1][y+1]="0";
System.out.print("7");
getPaths(n,p, x+1, y-1, word,MyLetteres);
}
if(x+1<MyLetteres.length&&y-1>0&&!MyLetteres[x+1][y-1].equals("0")){//up, left
word=word+""+MyLetteres[x+1][y-1];
Check(word);
reverse(word);
MyLetteres[x+1][y-1]="0";
System.out.print("8");
getPaths(n, p,x-1 , y +1, word,MyLetteres);
}
}
}