Найдите самый длинный путь в массиве символов

Question

Здравствуйте, и любая помощь очень ценится!

Мне нужно создать программу, которая проходит через массив символов, который считывает из файла.Затем программе необходимо использовать рекурсию, чтобы найти самый длинный последовательный путь из «А», которые смежны (не диагонали) с текущим «А».Он может посчитать каждый «А» только один раз, поэтому он не может вернуться назад, как только достигнет конца пути.Пример массива символов, с которым я работаю:

8 13
EAADDOAN
ATAFAWOB
ADAAAAIA
AWUYAAAA
ZAWAADDX
AAAAAAAZ
IMBAQJAA
AIAINOAK
AZVAJAAQ
VPNKAAAJ
TAAAWKAW
AAAAHRAV
ETEMAALA

Length of the longest A path is 23

8 обозначает столбцы, а 13 - строки массива.Я установил еще один логический массив, чтобы отслеживать, был ли уже подсчитан «А» или нет.Ниже приведен метод, который перебирает каждую позицию и вызывает рекурсивную функцию (выглядит довольно странно, впервые публикуя здесь):

public int findLongestPathLength() {
// TODO Auto-generated method stub
int i, j, x, y;
int numOfAs = 0;
int longestPath = 0;

// Create boolean array for checking if an 'A' has been counted or not
alreadyCounted = new boolean[numOfArrays][arrLength];

// Initialize all values in alreadyCounted array to false
for(i = 0; i < numOfArrays; i++) {
    for(j = 0; j < arrLength; j++ ) {
        alreadyCounted[i][j] = false;
    }
}

for(i = 0; i < numOfArrays; i++) {
    for(j = 0; j < arrLength; j++ ) {
        if(map[i][j] == 'A') {
            alreadyCounted[i][j] = true;
            numOfAs = findPathLengthRecursive(i, j) + 1;

/* If this iteration of finding the longest path of 'A's is the longest
    so far, replace the longestPath value with this number of A's */
if(numOfAs > longestPath)
    longestPath = numOfAs;

// Initialize all values in alreadyCounted array back to false
    for(x = 0; x < numOfArrays - 1; x++) {
        for(y = 0; y < arrLength - 1; y++ ) {
            alreadyCounted[x][y] = false;
        }
    }

// Reset currentLength in findPathLengthRecursive back to 0
    currentLength = 0;

}               
}
}

    return longestPath;
}

Созданный мной рекурсивный метод: public int findPathLengthRecursive (int i, intj) {// TODO Автоматически сгенерированный метод заглушки

    // To check if there is an 'A' to any of the sides of the current cell
    boolean left = true, right = true, up = true, down = true;

    /* Base case (when recursion should stop) is when there is no 'A's left to count in the path */ 
    if(j == 0 || (j > 0 && (map[i][j - 1] != 'A' || alreadyCounted[i][j - 1]))){
        left = false;
    }

    if(j == arrLength - 1 || (j < arrLength - 1 && (map[i][j + 1] != 'A' || alreadyCounted[i][j + 1]))) {
        right = false;
    }

    if(i == numOfArrays - 1 || (i < numOfArrays - 1 && (map[i + 1][j] != 'A' || alreadyCounted[i + 1][j]))) {
        down = false;
    }
    if(i == 0 || (i > 0 && (map[i - 1][j] != 'A' || alreadyCounted[i - 1][j]))) {
        up = false;
    }

    // If there is no valid 'A's around then return currentLength
    if(!left && !right && !down && !up) {
        return currentLength;
    } else {
        if(down && left && up && right) {
            alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
            alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
            alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
            alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
            currentLength += Math.max(Math.max(Math.max(findPathLengthRecursive(i + 1, j), findPathLengthRecursive(i, j - 1)), findPathLengthRecursive(i - 1, j)), findPathLengthRecursive(i, j + 1));
        }   
        else if(left && up && right) {
            alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
            alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
            alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
            currentLength += Math.max(Math.max(findPathLengthRecursive(i, j - 1), findPathLengthRecursive(i - 1, j)), findPathLengthRecursive(i, j + 1));
        }
        else if(up && right && down) {
            alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
            alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
            alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
            currentLength += Math.max(Math.max(findPathLengthRecursive(i - 1, j), findPathLengthRecursive(i, j + 1)), findPathLengthRecursive(i + 1, j));
        }
        else if(right && down && left) {
            alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
            alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
            alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
            currentLength += Math.max(Math.max(findPathLengthRecursive(i, j + 1), findPathLengthRecursive(i + 1, j)), findPathLengthRecursive(i, j - 1));
        }
        else if(down && left && up) {
            alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
            alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
            alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
            currentLength += Math.max(Math.max(findPathLengthRecursive(i + 1, j), findPathLengthRecursive(i, j - 1)), findPathLengthRecursive(i - 1, j));
        }
        else if(left && right) {
            alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
            alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
            currentLength += Math.max(findPathLengthRecursive(i, j - 1), findPathLengthRecursive(i, j + 1));

        } 
        else if(up && down) {
            alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
            alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
            currentLength += Math.max(findPathLengthRecursive(i - 1, j), findPathLengthRecursive(i + 1, j)); 
        }
        else if(left && up) {
            alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
            alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
            currentLength += Math.max(findPathLengthRecursive(i, j - 1), findPathLengthRecursive(i - 1, j));
        } 
        else if(left && down) {
            alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
            alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
            currentLength += Math.max(findPathLengthRecursive(i, j - 1), findPathLengthRecursive(i + 1, j));
        } 
        else if(right && up) {
            alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
            alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
            currentLength += Math.max(findPathLengthRecursive(i, j + 1), findPathLengthRecursive(i - 1, j));
        }
        else if(right && down) {
            alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
            alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
            currentLength += Math.max(findPathLengthRecursive(i, j + 1), findPathLengthRecursive(i + 1, j));
        } 
        else if(left) {
            currentLength++;
            alreadyCounted[i][j - 1] = true; // Show that this 'A' has already been counted
            findPathLengthRecursive(i, j - 1); 
        }
        else if(up) {
            currentLength++;
            alreadyCounted[i - 1][j] = true; // Show that this 'A' has already been counted
            findPathLengthRecursive(i - 1, j); 
        }
        else if(right) {
            currentLength++;
            alreadyCounted[i][j + 1] = true; // Show that this 'A' has already been counted
            findPathLengthRecursive(i, j + 1); 
        }
        else if(down) {
            currentLength++;
            alreadyCounted[i + 1][j] = true; // Show that this 'A' has already been counted
            findPathLengthRecursive(i + 1, j); 
        }

    }
    return currentLength;

}

Неважно, что я пытаюсь. Кажется, я просто возвращаю случайные числа, которые не близки к 23, которые я ищу.

Это результат рекурсивного метода, когда он вызывается из первого метода.

136 70 1 3 70 58 1 56 70 36 37 1 3 60 53 69 85 66 69 85 6654 43 63 51 49 79 84 109 142 2 1 139 2 1 87 116 119 118 132 3 4 3 100 5 4 2 1 166 2 1 1 166

Любая помощь будет очень полезна, спасибо!

Answer 1

Решение уже есть, но я думаю, что оно не сбрасывает посещенное состояние должным образом, что может привести к тому, что оно пропускает важные параметры пути (предыдущая проблема суммы и максимума, по-видимому, была исправлена ​​в это время).

Если вы хотите чему-то научиться, исправить и улучшить свое собственное, я бы порекомендовал перенести всю логику в начало рекурсивной функции:

• Находится ли исследуемая позиция в пределах границ?
• Это «А»?
• Не учитывалось ли уже?

Если какое-либо условие ложно, просто выйдите досрочно, вернув 0.

Это позволяет вам просто пометить позицию, подсчитанную после проверок, а затем вызвать метод рекурсивно для всех направлений.без обширных проверок и возврата максимального + 1. Вы можете вызвать недопустимые позиции, как это проверено внутри рекурсивной функции.Не забудьте использовать результат рекурсивного вызова.

Не повторение проверок позволит избежать ошибок копирования-вставки и дополнительных циклов или необходимости использования массивов направлений.

Не забудьтеснимите отметку при выходе из рекурсивной функции.

Редактировать : псевдокод, чтобы лучше проиллюстрировать упрощение (вам нужно заменить комментарии и «...» на соответствующий код):

 public int findPathLengthRecursive(int i, int j) {
   if (i < 0 || j < 0 || i >= ... ) {
     return 0;
   }

   // Check here that there is an A at the position, otherwise return 0

   // Mark the current position as visited here

   int result = 1 + Math.max(
       Math.max(
          findPathLengthRecursive(i - 1, j),
          findPathLengthRecursive(i + 1, j)),
       Math.max(
          findPathLengthRecursive(i, j - 1),
          findPathLengthRecursive(i, j + 1)));

   // Remove the mark for the current position here

   return result;
 } 

В основном

1. Проверка всего в начале рекурсивной функции исключает необходимость многократных (подверженных ошибкам) ​​проверок при выполнении рекурсивного вызова
2. МеткаНеобходимо удалить при возвращении из рекурсии, чтобы проверить альтернативы
3. , возвращаемые значения из рекурсии должны быть учтены должным образом.

Answer 2

char [][]mat;

boolean visit[][];

int rowSize , columnSize;

int dx[] = {-1 , 0  ,  0 , +1};
int dy[] = { 0 , +1 , -1 ,  0};

int rec(int row , int col){

    visit[row][col] = true;

    int ret = 0;

    for(int k = 0 ; k < 4 ; ++k){
        int nr = row+dx[k];
        int nc = col+dy[k];

        if(nr < 0 || nr >= rowSize || nc < 0 || nc >= columnSize || visit[nr][nc] && mat[nr][nc] != 'A'){   
            continue;       
        }
        ret += 1 + rec(nr , nc);
    }

    return ret;

}


void main(){
    //todo input the matris and rowSize , columnSize

    //todo make all item of visit by 0;

    int mx = 0;
    for(int i = 0 ; i < rowSize; ++i){
        for(int j = 0 ; j < columnSize; ++j){
            int cur = rec(i ,j);
            mx = mx > cur ? mx : cur;
        }
    }

    //mx is answer

}