هڪ ميٽرڪس ۾ پيلنروڊڪ رستن جو تعداد


تڪليف جي سطح سخت
بار بار پڇڻ ۾ ايپل ڪوڊشن ڪريو فاتح گوگل
متحرڪ پروگرامنگ قائم ٿينديون پلاڻوموم

مسئلي جو بيان

اسان کي ٻه ٻه ماڙ معنائون ڏني وئي جن ۾ ننcaseا نن Englishا سنڌي الفابيٽ شامل آهن ، اسان کي انهي ۾ پيلنڊرومڪ رستن جو انگ ڳڻڻ گهرجي. هڪ پيلوودروڪڪ رستو پيلاندرومڪ ملڪيت جي پيروي ڪندڙ رستو کانسواءِ ڪجهه به ناهي. هڪ لفظ جيڪو جڏهن ڪنڌ کڻي وڃي اهو ساڳيو ئي رهي ٿو جيترو شروعاتي لفظ هڪ پايلنڊروم چيو وڃي ٿو. اسان کي شروعاتي نقطي کان منزل تائين رستي جي تعداد جي ڳڻپ ڪرڻ گهرجي. اسان جو شروعاتي نقشو مٿيون کاٻي خانو آهي ۽ منزل هيٺيون سا cornerي ڪنڊ آهي. تحريڪ جي هدايت تي پڻ هڪ شرط لاڳو ڪئي وئي آهي. اسان موجوده سيل کان صحيح ۽ هيٺيون طرف منتقل ڪريون ٿا.

مثال

هڪ ميٽرڪس ۾ پيلنروڊڪ رستن جو تعداد

Matrix = { a a b

           a z a

           b a a }
6

وضاحت: 6 ڏنل طريقا آهن هڪ ڏنل ميٽرڪس مان پيلنرومروڪ جو رستو حاصل ڪرڻ جي لاءِ. ڇاڪاڻ ته اسان صرف شروعاتي نقشي (0,0،0,1) کان (1,0،XNUMX) ۽ (XNUMX،XNUMX) طرف منتقل ٿي سگهون ٿا.

چار رستا آهن ابا ، آفا ، عزا ، عفا ، عزا ، عازه. رستن جا ٻه ساڳيا آهن. ڇو ته ڏنل ميٽرڪس بنيادي تشبيهن بابت سميري آهي. اهو ئي سبب آهي ڇاڪاڻ ته اسان جا ٻه ساڳيا پيلنڊيرومڪ رستا آهن.

{a}
1

وضاحت: ڇاڪاڻ ته هتي فقط واحد رستو “الف” آهي جيڪو پڻ هڪ پلنڊروم آهي. جواب 1 آهي.

ميٽرڪس جي مسئلي ۾ پيلنڊررومڪ رستن جي تعداد جي رٿا

نائي اچڻ وارو

هن مسئلي ۾ ، اسين پسمنظر استعمال ڪنداسين رستن جي هر ممڪن ترتيب ڳوليندا ۽ پوءِ چڪاس ڪريون ته رستو پيلنڊروم آهي يا نه. استعمال ٿيل پٺتي پيل ٻڌائڻ کان اڳ چيو ويو جيڪو ڪافي ڪارائتو نه آهي. جتان واپس هلڻ هر ممڪن حل پيدا ڪري ٿي. اسان انهن سڀني حلن جي چڪاس ڪريو جيڪڏهن اهي آهن پيچندرو. جئين هي ڪافي ڪارائتو ناهي اسان اسان شروعاتي نقطي ۽ منزل کان رستي ۾ الف جي لاءِ ٻه متغير رکون.

ايڏي موثر رستو

هاڻي ، اسان پنهنجي الگورتھم کي مختصر ڪري سگھون ٿا. اسان ٻن متغيرن کي استعمال ڪندا آهيون جيڪي سيلز کي اسٽور ڪن ٿيون ، هڪ شروعات کان ۽ هڪ آخر کان. اهي ٻئي ذخيرا ڪيل متغير ساڳيا هجڻ گهرجي پاللرومريڪ ملڪيت کي مطمئن ڪرڻ جي لاءِ. اسان اڳتي وڌو جيڪڏھن الفابيٽ ساڳيو آھي. اڳتي وڌڻ جي ذريعي ، منهنجو مطلب آھي ته اسين ھر ممڪن سمت لاءِ ماتحت ڪال جي لاءِ دعوتي ڪال ڪريون. جڏهن ته اسان وٽ سازگار حل آهي. اسان سوچون ٿا متحرڪ پروگرامنگ جيڪڏهن اتي ڪو به وڌيڪ ذيلي عنصر موجود آهن. جيئن ته اسان ڪيترائي ضمني مسئلا ڪيترائي ڀيرا حل ڪري سگهنداسين ، جيڪڏهن اسان انهن جا نتيجا محفوظ ڪنداسين ته بهتر آهي. اسان ذيلي مضمون جي نتيجي کي محفوظ ڪرڻ لاءِ هڪ نقشو استعمال ڪري سگهون ٿا. شروعاتي ۽ ختم ٿيڻ واري خندقن جا اشارا نقشي جي ڪُنجي طور ڪم ڪندا آهن. اهو ائين آهي ته اسان هڪ 2D صف ۾ پيلنڊروومڪڪ رستن جو تعداد ڳوليندا آهيون

ميٽرڪس جي مسئلي ۾ پيليرومروڪ رستن جي تعداد لاءِ ڪوڊ

سي ++ ڪوڊ

#include <bits/stdc++.h>
using namespace std;

// checks if index i,j is valid or not (lies inside matrix or not)
bool isValid (int n, int m, int i, int j) {
    return !(i < 0 || i >= n || j < 0 || j >= m);
}

// return number of palindromic paths in matrix
int solvePalindromicPaths(vector<vector<char>> &matrix, int startRow, int startCol, int endRow, int endCol, map<pair<pair<int,int>,pair<int,int>>,int> &dp) {
    int n = matrix.size(), m = matrix[0].size();
    
    // check if start and end cell indices are valid (are inside matrix)
    if (!isValid(n, m, startRow, startCol) || !isValid(n, m, endRow, endCol))
        return 0;
    // if start indices are after end indices, they can not meet in middle
    if (startRow > endRow || startCol > endCol)
    return 0;
    // if path does not follow palindromic property
    if (matrix[startRow][startCol] != matrix[endRow][endCol])
        return 0;
    // indices are adjacent to each other
    if (abs((startRow - endRow) + (startCol - endCol)) <= 1)
        return 1;
    // store indices as pair, since our map is using indices as key
    pair<pair<int,int>,pair<int,int>> indices = pair<pair<int,int>,pair<int,int>>
                                                (pair<int,int>(startRow, startCol), pair<int,int>(endRow, endCol));
                                                
    // if sub-problem has alredy been calculated
    if(dp.count(indices))
        return dp[indices];
        
    // if not calculated, calculate result by recursively calling in all directions
    int countOfPalindromicPaths = 0;
    countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow + 1, startCol, endRow - 1, endCol, dp);
    countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow + 1, startCol, endRow, endCol - 1, dp);
    countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow, startCol + 1, endRow - 1, endCol, dp);
    countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow, startCol + 1, endRow, endCol - 1, dp);
    
    // store and return the result
    return dp[indices] = countOfPalindromicPaths;
}

int main() {
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        vector<vector<char>> matrix(n, vector<char>(m));
        map<pair<pair<int,int>,pair<int,int>>,int> dp;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
            cin>>matrix[i][j];
        }
        cout<<solvePalindromicPaths(matrix, 0, 0, n-1, m-1, dp)<<endl;
    }
}
2
2 2
a b
b a
3 3
a a b
a z a
b a a
2
6

جاوا ڪوڊ

import java.util.*;
import java.lang.*;
import java.io.*;

class Indices {
    private int startRow;
    private int startCol;
    private int endRow;
    private int endCol;

    public Indices(int startRow, int startCol, int endRow, int endCol) {
        this.startRow = startRow;
        this.startCol = startCol;
        this.endRow = endRow;
        this.endCol = endCol;
    }
}

public class Main {

    // checks if index i,j is valid or not (lies inside matrix or not)
    static boolean isValid (int n, int m, int i, int j) {
        return !(i < 0 || i >= n || j < 0 || j >= m);
    }

    // return number of palindromic paths in matrix
    static int solvePalindromicPaths(char[][] matrix, int startRow, int startCol, int endRow, int endCol, int n, int m, HashMap<Indices, Integer> dp) {
        // check if start and end cell indices are valid (are inside matrix)
        if (!isValid(n, m, startRow, startCol) || !isValid(n, m, endRow, endCol))
            return 0;
        // if start indices are after end indices, they can not meet in middle
        if (startRow > endRow || startCol > endCol)
            return 0;
        // if path does not follow palindromic property
        if (matrix[startRow][startCol] != matrix[endRow][endCol])
            return 0;
        // indices are adjacent to each other
        if (Math.abs((startRow - endRow) + (startCol - endCol)) <= 1)
            return 1;
        // create an instance of indices with current values, since our map is using indices as key
        Indices indices = new Indices(startRow, startCol, endRow, endCol);

        // if sub-problem has alredy been calculated
        if(dp.containsKey(indices))
            return dp.get(indices);

        // if not calculated, calculate result by recursively calling in all directions
        int countOfPalindromicPaths = 0;
        countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow + 1, startCol, endRow - 1, endCol, n, m, dp);
        countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow + 1, startCol, endRow, endCol - 1, n, m, dp);
        countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow, startCol + 1, endRow - 1, endCol, n, m, dp);
        countOfPalindromicPaths += solvePalindromicPaths(matrix, startRow, startCol + 1, endRow, endCol - 1, n, m, dp);

        // store and return the result
        dp.put(indices, countOfPalindromicPaths);
        return countOfPalindromicPaths;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- > 0){
            int n = sc.nextInt();
            int m = sc.nextInt();
            char matrix[][] = new char[n][m];

            HashMap<Indices, Integer> dp = new HashMap<>();
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++) {
                    matrix[i][j] = sc.next().charAt(0);
                }
            }
            System.out.println(solvePalindromicPaths(matrix, 0, 0, n-1, m-1, n, m, dp));
        }
    }
}
2
2 2
a b
b a
3 3
a a b
a z a
b a a
2
6

پيچيدگي تجزيي

وقت جي پيچيدگي: اي (اين * ايم)

جتان اسان سب سبيلبلز جو نتيجو اسٽور ڪري رهيا آهيون. ڇو ته مجموعي طور N * M رياستون آهن. اسان وٽ وقت جي پيچيدگي آهي O (N * M) ، جنهن جو مطلب آهي هڪ ميٽرڪس مسئلي ۾ پيلنومروڪڪ رستن جو تعداد پولونوميل وقت جي پيچيدگي آهي.

خلائي پيچيدگي: اي (اين * ايم)

هتي صرف اين * ايم رياستون آهن ، خلائي پيچيدگي اي (اين * ايم) آهي.