다른 문자의 행렬이 제공됩니다. 한 문자에서 시작하여 현재 문자보다 큰 모든 문자를 순회하여 가장 긴 경로를 찾아야 합니다. 문자는 서로 연속적입니다.
가장 긴 경로를 찾기 위해 우리는 깊이 우선 탐색 알고리즘을 사용할 것입니다. DFS 동안 일부 하위 문제가 여러 번 발생할 수 있습니다. 그 계산을 피하기 위해 우리는 동적 프로그래밍 방식을 계속해서 사용할 것입니다.
입력 및 출력
Input: The matrix as shown above. And the starting point. Here the starting point is e. Output: Enter Starting Point (a-i): e Maximum consecutive path: 5
알고리즘
findLongestLen(i, j, 이전)
입력: 위치 i, j 및 이전 문자.
출력: 가장 긴 길이.
Begin if (i, j) place is valid or prev and matrix[i,j] are adjacent, then return 0 if longestPath[i, j] is already filled, then return longestPath[i, j] len := 0 for all its nearest 8 rooms k, do len := maximum of len and (1 + findLongestLen(i, x[k], j +y[k], matrix[i, j])) done longestPath[i, j] := len return len End
getLen(시작)
입력 - 시작 지점.
출력 - 최대 길이.
Begin for all row r of matrix, do for all column c, of matrix, do if matrix[i, j] = start, then for all adjacent room k, do len := maximum of len and (1 + findLongestLen(i, x[k], j +y[k], matrix[i, j]))) done done done return len End
예
#include<iostream> #define ROW 3 #define COL 3 using namespace std; // tool matrices to recur for adjacent cells. int x[] = {0, 1, 1, -1, 1, 0, -1, -1}; int y[] = {1, 0, 1, 1, -1, -1, 0, -1}; int longestPath[ROW][COL]; char mat[ROW][COL] = { {'a','c','d'}, {'h','b','a'}, {'i','g','f'} }; int max(int a, int b) { return (a>b)?a:b; } bool isvalid(int i, int j) { if (i < 0 || j < 0 || i >= ROW || j >= COL) //when i and j are in range return false; return true; } bool isadjacent(char previous, char current) { return ((current - previous) == 1); //check current and previous are adjacent or not } int findLongestLen(int i, int j, char prev) { if (!isvalid(i, j) || !isadjacent(prev, mat[i][j])) //when already included or not adjacent return 0; if (longestPath[i][j] != -1) return longestPath[i][j]; //subproblems are solved already int len = 0; // Initialize result to 0 for (int k=0; k<8; k++) //find length of the largest path recursively len = max(len, 1 + findLongestLen(i + x[k], j + y[k], mat[i][j])); return longestPath[i][j] = len; // save the length and return } int getLen(char start) { for(int i = 0; i<ROW; i++) for(int j = 0; j<COL; j++) longestPath[i][j] = -1; //set all elements to -1 int len = 0; for (int i=0; i<ROW; i++) { for (int j=0; j<COL; j++) { // check for all possible starting point if (mat[i][j] == start) { for (int k=0; k<8; k++) //for all eight adjacent cells len = max(len, 1 + findLongestLen(i + x[k], j + y[k], start)); } } } return len; } int main() { char start; cout << "Enter Starting Point (a-i): "; cin >> start; cout << "Maximum consecutive path: " << getLen(start); return 0; }
출력
Enter Starting Point (a-i): e Maximum consecutive path: 5