Шумораи роҳҳои палиндромикӣ дар матритса


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад себ CodeNation Facebook Фараж Google
Барномарезии динамикӣ Matrix Палиндромҳо

Изҳороти мушкилот

Ба мо матритсаи дуандоза дода шудааст, ки алифбои хурди англисиро дар бар мегирад, ба мо лозим аст, ки шумораи роҳҳои палиндромиро дар он ҳисоб кунем. Роҳи палиндромикӣ чизе ҷуз роҳи пайравӣ аз амволи палиндромикӣ нест. Калимае, ки ҳангоми баргардонидан бо калимаи аввал боқӣ мемонад, палиндром гуфта мешавад. Мо бояд шумораи роҳҳоро аз нуқтаи аввал то таъинот ҳисоб кунем. Нуқтаи ибтидоии мо чашмаки чапи боло ва таъинот гӯшаи поёни рост мебошад. Инчунин шарте мавҷуд аст, ки ба самти ҳаракат гузошта шудааст. Мо аз чашмаки ҷорӣ ба самти рост ва поён ҳаракат мекунем.

мисол

Шумораи роҳҳои палиндромикӣ дар матритса

Matrix = { a a b

           a z a

           b a a }
6

Шарҳ: 6 роҳи ба даст овардани роҳи палиндромикӣ аз матритсаи додашуда вуҷуд дорад. Зеро мо метавонем танҳо аз нуқтаи ибтидоӣ (0,0) ба (0,1) ва (1,0) гузарем.

Чор роҳ - аабаа, аазаа, аазаа, аабаа, ааааа, аазаа. Ҳарду пайроҳа ба ҳам монанданд. Азбаски матритсаи додашуда нисбати диагонали асосӣ симметрия аст. Ин сабаби он аст, ки мо ду роҳи палиндромикии шабеҳ дорем.

{a}
1

Шарҳ: Азбаски танҳо як пайраҳаи "а" вуҷуд дорад, ки он низ палиндром аст. Ҷавоб 1.

Равиш ба шумораи роҳҳои палиндромикӣ дар масъалаи матритса

Усули соддалавҳона

Дар ин масъала, мо рекурсияро истифода бурда ҳамаи пайдарпаии имконпазири пайраҳаҳоро пайдо мекунем ва пас пай мебарем, ки роҳ палиндром аст ё не. Равише, ки қаблан пуштибонӣ карда мешуд, гуфт, ки ба қадри кофӣ самарабахш нест. Азбаски backtracking ҳамаи ҳалли имконпазирро тавлид мекунад. Мо ҳамаи ин қарорҳоро тафтиш мекунем, агар онҳо бошанд палиндром. Азбаски ин ба қадри кофӣ самаранок нест, мо ду аломатҳои алифборо дар роҳ аз нуқтаи аввал ва таъинот нигоҳ медорем.

Усули самаранок

Ҳоло, мо метавонем алгоритми худро ҷамъбаст кунем. Мо ду тағирёбандаро истифода мебарем, ки ҳуҷайраҳоро нигоҳ медоранд, яке аз аввал ва дигаре аз охир. Ин ду тағирёбандаи захирашуда бояд барои қонеъ кардани хосияти палиндромикӣ якхела бошанд. Агар ҳарфҳо якхела бошанд, мо пеш меравем. Бо пеш рафтан, ман дар назар доштам, ки мо даъвати рекурсивӣ ба зерпроблемаро дар ҳама самтҳои имконпазир анҷом медиҳем. Ҳар вақте ки мо ҳалли рекурсивӣ дорем. Мо метавонем дар бораи он фикр кунем барномасозии динамикӣ агар зерпроблемаҳои такроршаванда мавҷуд бошанд. Азбаски мо якчанд зерпроблемаҳоро якчанд маротиба ҳал хоҳем кард, беҳтараш натиҷаҳои онҳоро нигоҳ дорем. Мо метавонем харитаро барои нигоҳ доштани натиҷаи зерпроблема истифода барем. Нишондиҳандаҳои оғоз ва хотимаи ҳуҷайраҳо ҳамчун калиди харита хизмат мекунанд. Ҳамин тавр мо шумораи пайраҳаҳои палиндромиро дар массиви 2D пайдо мекунем

Код барои шумораи роҳҳои палиндромикӣ дар масъалаи матритса

Кодекси C ++

#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

Кодекси Java

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

Таҳлили мураккабӣ

Мураккабии вақт: O (N * M)

Азбаски мо натиҷаи зерпроблемаҳоро нигоҳ медорем. Зеро дар он ҷо ҳамагӣ давлатҳои N * M мавҷуданд. Мо мураккабии вақтии O (N * M) дорем, ки маънои шумораи роҳҳои палиндромиро дар масъалаи матрица мураккабии вақти полиномӣ дорад.

Мураккабии фазо: O (N * M)

Азбаски танҳо ҳолатҳои N * M мавҷуданд, мураккабии фазо O (N * M) мебошад.