एक वर्ग मैट्रिक्स[][] दिया गया है जिसमें गैर-ऋणात्मक संख्याएं इसके तत्वों के रूप में हैं। साथ ही एक वेरिएबल स्कोर दिया गया है। लक्ष्य मैट्रिक्स[][] से तत्वों को जोड़कर दिए गए स्कोर तक पहुंचने के तरीकों की गिनती करना है जैसे कि केवल दाएं और नीचे की चालें अनुमत हैं।
matrix[0][0] से शुरू करके केवल चालें हो सकती हैं, matrix[0][1] पर जाएं (दायां कदम) या matrix[1][0] पर जाएं (नीचे का कदम) और योग=स्कोर तक पहुंचने के लिए मान जोड़ें।
उदाहरणों से समझते हैं।
उदाहरण के लिए
इनपुट - matrix[row][col] = { {1, 1}, { 1, 1} } score=3
आउटपुट - मैट्रिक्स में दिए गए स्कोर तक पहुंचने के तरीकों की संख्या: 2
व्याख्या - स्कोर निम्नलिखित तरीकों से पहुंचा जा सकता है:
तरीका 1: इंडेक्स (0,0) + (0,1) + (1,1) पर तत्व जोड़ना = 1+1+1 = 3
तरीका 2: इंडेक्स (0,0) + (1,0) + (1,1) पर तत्व जोड़ना = 1+1+1 = 3
इनपुट - matrix[row][col] = { {1,1,2},{ 2,1,1}, {1,2,2} } score=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
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
इस दृष्टिकोण में हम समस्या को हल करने के लिए डायनामिक प्रोग्रामिंग का उपयोग करेंगे। हम दो सरणी arr[row][col][size] और check[row][col][size] का उपयोग करेंगे। सरणी check मैट्रिक्स[][] के सेल्स को देखा गया के रूप में true से चिह्नित करेगी। सरणी arr[][][] का उपयोग matrix[0][0] से किसी विशेष सेल तक पहुंचने के तरीकों की संख्या संग्रहीत करने के लिए किया जाता है। पुनरावर्ती रूप से हम तरीकों की गणना करेंगे।
- संख्याओं को संग्रहीत करने के लिए 2D सरणी मैट्रिक्स लें।
- वेरिएबल स्कोर को इनपुट के रूप में लें।
- दो सरणी int arr[row][col][size] और bool check[row][col][size] लें।
- फ़ंक्शन matrix_score(int matrix[row][col], int rows, int cols, int sc) का उपयोग मैट्रिक्स में दिए गए स्कोर तक पहुंचने के तरीकों की संख्या लौटाने के लिए किया जाता है।
- यदि स्कोर sc 0 से कम है तो 0 लौटाएं। (पुनरावृत्ति समाप्त करने के लिए या गलत इनपुट के मामले में)
- यदि पंक्तियों या स्तंभों की संख्या 0 से कम है तो 0 लौटाएं। (पुनरावृत्ति समाप्त करने के लिए)।
- यदि पहला सेल इनपुट स्कोर sc के बराबर है तो 1 लौटाएं एकमात्र तरीके के रूप में। यदि नहीं तो 0 लौटाएं।
- यदि वर्तमान सेल पहले से देखा गया है, तो इस सेल पर तरीकों की संख्या arr[rows][cols][sc] के रूप में लौटाएं।
- यदि उपरोक्त सभी शर्तें लागू नहीं होतीं तो वर्तमान सेल को देखा गया चिह्नित करें। check[rows][cols][sc] = true का उपयोग करके।
- temp_1 = matrix_score(matrix, rows-1, cols, sc-matrix[rows][cols]) की गणना करें
- temp_2 = matrix_score(matrix, rows, cols-1, sc-matrix[rows][cols]) की गणना करें
- तरीकों की संख्या को arr[rows][cols][sc] = temp_1 + temp_2 के रूप में सेट करें।
- अंत में arr[rows][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
