एक वर्ग मैट्रिक्स को देखते हुए [] [] जिसमें इसके तत्वों के रूप में गैर ऋणात्मक संख्याएँ हों। एक परिवर्तनीय स्कोर भी दिया। लक्ष्य मैट्रिक्स [] [] से तत्वों को जोड़कर दिए गए स्कोर तक पहुंचने के तरीकों की गणना करना है, जैसे कि केवल चाल की अनुमति सही चाल और नीचे की चाल है।
मैट्रिक्स से शुरू [0] [0] केवल चालें हो सकती हैं, मैट्रिक्स [0] [1] (दाएं चाल) पर जाएं या मैट्रिक्स [1] [0] (डाउन मूव) पर जाएं और योग =स्कोर तक पहुंचने के लिए मूल्य जोड़ें।
आइए उदाहरणों से समझते हैं।
उदाहरण के लिए
इनपुट - मैट्रिक्स [पंक्ति] [कॉल] ={ {1, 1}, { 1, 1} } स्कोर=3
आउटपुट - मैट्रिक्स में दिए गए स्कोर तक पहुंचने के तरीकों की संख्या हैं:2
स्पष्टीकरण - स्कोर निम्नलिखित तरीकों से पहुँचा जा सकता है:
तरीका 1:इंडेक्स (0,0) + (0,1) + (1,1) =1+1+1 =3
पर एलिमेंट जोड़नातरीका 2:इंडेक्स पर एलिमेंट जोड़ना (0,0) + (1,0) + (1,1) =1+1+1 =3
इनपुट - मैट्रिक्स [पंक्ति] [कॉल] ={ {1,1,2}, { 2,1,1}, {1,2,2} } स्कोर=7
आउटपुट - मैट्रिक्स में दिए गए स्कोर तक पहुंचने के तरीकों की संख्या हैं:2
स्पष्टीकरण - स्कोर निम्नलिखित तरीकों से पहुँचा जा सकता है:
तरीका 1:इंडेक्स पर एलिमेंट जोड़ना (0,0) + (0,1) + (1,1) + (1,2) + (2,2) =1+1+1+2+2 =7
तरीका 2:इंडेक्स पर एलिमेंट जोड़ना (0,0) + (0,1) + (1,1) + (2,1) + (2,2) =1+1+1+2+2 =7
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में हम समस्या को हल करने के लिए गतिशील प्रोग्रामिंग का उपयोग करेंगे। हम दो सरणियों का उपयोग करेंगे गिरफ्तारी [पंक्ति] [कॉल] [आकार] और जांच [पंक्ति] [कॉल] [आकार]। सरणी जांच मैट्रिक्स [] [] की कोशिकाओं को चिह्नित करेगी यदि वे सत्य के रूप में देखी जाती हैं। ऐरे एआर [] [] [] का उपयोग मैट्रिक्स से किसी विशेष सेल तक पहुंचने के तरीकों की संख्या को संग्रहीत करने के लिए किया जाता है [0] [0]। पुनरावर्ती रूप से हम तरीकों की गणना करेंगे।
- संख्याओं को संग्रहीत करने के लिए 2D सरणी मैट्रिक्स लें।
- वेरिएबल स्कोर को इनपुट के रूप में लें।
- दो सरणियाँ लें int arr[row][col][size] और bool check[row][col][size].
- फ़ंक्शन मैट्रिक्स_स्कोर (इंट मैट्रिक्स [पंक्ति] [कॉल], इंट रो, इंट कॉल्स, इंट एससी) का उपयोग मैट्रिक्स में दिए गए स्कोर तक पहुंचने के तरीकों की संख्या को वापस करने के लिए किया जाता है।
- यदि स्कोर एससी 0 से कम है तो 0 लौटाएं। (पुनरावृत्ति समाप्त करने के लिए या गलत इनपुट के मामले में)
- यदि पंक्तियों या स्तंभों की संख्या 0 से कम है तो 0 पर लौटें। (पुनरावृत्ति समाप्त करने के लिए)।
- यदि पहली सेल sc (इनपुट स्कोर) के बराबर है तो 1 को ही एकमात्र तरीका के रूप में लौटाएं। अगर ऐसा नहीं है तो 0 वापस करें।
- यदि वर्तमान सेल पहले ही देखी जा चुकी है, तो इस सेल में आने वाले तरीकों की संख्या को arr[rows][cols][sc] के रूप में लौटाएं।
- यदि उपरोक्त सभी शर्तें लागू नहीं होती हैं तो वर्तमान सेल को विज़िट किया गया के रूप में चिह्नित करें। check[rows][cols][sc] =true. . का उपयोग करना
- temp_1 =मैट्रिक्स_स्कोर की गणना करें (मैट्रिक्स, रो -1, कोल्स, एससी-मैट्रिक्स [पंक्तियां] [कॉल्स])
- temp_2 =मैट्रिक्स_स्कोर की गणना करें (मैट्रिक्स, पंक्तियाँ, कॉलम -1, एससी-मैट्रिक्स [पंक्तियाँ] [कॉल्स])
- गिरफ्तारी [पंक्तियों] [cols] [sc] =temp_1 + temp_2 के रूप में तरीकों की संख्या सेट करें।
- अंत में वापसी गिरफ्तारी [पंक्तियों] [cols] [sc]।
उदाहरण
#include <iostream>
using namespace std;
#define row 2
#define col 2
#define size 30
int arr[row][col][size];
bool check[row][col][size];
int matrix_score(int matrix[row][col], int rows, int cols, int ways) {
if (ways < 0) {
return 0;
}
if (rows < 0 || cols < 0) {
return 0;
}
if (rows == 0) {
if (cols == 0) {
if (ways == matrix[0][0]) {
return 1;
} else {
return 0;
}
}
}
if (check[rows][cols][ways]) {
return arr[rows][cols][ways];
}
check[rows][cols][ways] = true;
int temp_1 = matrix_score(matrix, rows - 1, cols, ways - matrix[rows][cols]);
int temp_2 = matrix_score(matrix, rows, cols - 1, ways - matrix[rows][cols]);
arr[rows][cols][ways] = temp_1 + temp_2;
return arr[rows][cols][ways];
}
int main() {
int matrix[row][col] = {
{
1,
1
},
{
1,
1
}
};
int ways = 3;
cout << "Count of number of ways to reach a given score in a Matrix are: " << matrix_score(matrix, row - 1, col - 1, ways);
return 0;
} यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
आउटपुट
Count of number of ways to reach a given score in a Matrix are: 2