दिए गए प्रारंभिक कैरेक्टर से सबसे लंबा क्रमागत पथ

विभिन्न कैरेक्टर्स का एक मैट्रिक्स दिया गया है। एक कैरेक्टर से शुरू करके, हमें वर्तमान कैरेक्टर से बड़े उन सभी कैरेक्टर्स को ट्रैवर्स करके सबसे लंबा पथ ढूंढना है। कैरेक्टर्स एक-दूसरे के क्रमागत हैं।

सबसे लंबा पथ ढूंढने के लिए, हम डेप्थ फर्स्ट सर्च (DFS) एल्गोरिदम का उपयोग करेंगे। DFS के दौरान, कुछ सबप्रॉब्लम्स कई बार उत्पन्न हो सकते हैं। उन बार-बार की गणना से बचने के लिए, हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।

इनपुट और आउटपुट

इनपुट: ऊपर दिखाया गया मैट्रिक्स। और प्रारंभिक बिंदु। यहां प्रारंभिक बिंदु 'e' है।
आउटपुट: Enter Starting Point (a-i): e
Maximum consecutive path: 5

एल्गोरिदम

findLongestLen(i, j, prev)

इनपुट: पोजीशन i और j और पिछला कैरेक्टर।

आउटपुट: सबसे लंबी लंबाई।

शुरुआत
    यदि (i, j) स्थान वैध है या prev और matrix[i,j] आसन्न हैं, तो
        वापस 0
    यदि longestPath[i, j] पहले से भरा है, तो
        वापस longestPath[i, j]
    len := 0
    इसके सभी निकटतम 8 कमरों k के लिए, करें
        len := len और (1 + findLongestLen(i, x[k], j + y[k], matrix[i, j])) का अधिकतम
    पूर्ण
    longestPath[i, j] := len
    वापस len
अंत

getLen(start)

इनपुट: प्रारंभिक बिंदु।

आउटपुट: अधिकतम लंबाई।

शुरुआत
    मैट्रिक्स की सभी पंक्तियों r के लिए, करें
        मैट्रिक्स के सभी कॉलम c के लिए, करें
            यदि matrix[i, j] = start, तो
                सभी आसन्न कमरों k के लिए, करें
                    len := len और (1 + findLongestLen(i, x[k], j + y[k], matrix[i, j]))) का अधिकतम
                पूर्ण
            पूर्ण
        पूर्ण
    पूर्ण
    वापस len
अंत

उदाहरण (C++ कोड)

#include <iostream>
#define ROW 3
#define COL 3
using namespace std;

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)
        return false;
    return true;
}

bool isadjacent(char previous, char current) {
    return ((current - previous) == 1);
}

int findLongestLen(int i, int j, char prev) {
    if (!isvalid(i, j) || !isadjacent(prev, mat[i][j]))
        return 0;
    if (longestPath[i][j] != -1)
        return longestPath[i][j];
    
    int len = 0;
    for (int k = 0; k < 8; k++)
        len = max(len, 1 + findLongestLen(i + x[k], j + y[k], mat[i][j]));
    
    return longestPath[i][j] = len;
}

int getLen(char start) {
    for(int i = 0; i < ROW; i++)
        for(int j = 0; j < COL; j++)
            longestPath[i][j] = -1;
    
    int len = 0;
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            if (mat[i][j] == start) {
                for (int k = 0; k < 8; k++)
                    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