กำหนดเมทริกซ์[][] แบบสี่เหลี่ยมจัตุรัสที่มีตัวเลขไม่ติดลบเป็นสมาชิก ยังมีตัวแปร score อีกตัว เป้าหมายคือนับวิธีไปถึงคะแนนที่กำหนดโดยการบวกสมาชิกจาก matrix[][] โดยที่การเคลื่อนที่ที่อนุญาตคือขวาและล่างเท่านั้น
เริ่มจาก matrix[0][0] การเคลื่อนที่ที่เป็นไปได้คือไป matrix[0][1] (ขวา) หรือ matrix[1][0] (ล่าง) และบวกค่าเพื่อให้ผลรวม = score
ทำความเข้าใจด้วยตัวอย่าง
ตัวอย่าง
Input - matrix[row][col] = {{1, 1}, {1, 1}} score = 3
Output - จำนวนวิธีไปถึงคะแนนที่กำหนดในเมทริกซ์คือ: 2
คำอธิบาย - คะแนนสามารถไปถึงได้ด้วยวิธีต่อไปนี้:
วิธี 1: บวกสมาชิกที่ดัชนี (0,0) + (0,1) + (1,1) = 1+1+1 = 3
วิธี 2: บวกสมาชิกที่ดัชนี (0,0) + (1,0) + (1,1) = 1+1+1 = 3
Input - matrix[row][col] = {{1,1,2}, {2,1,1}, {1,2,2}} score = 7
Output - จำนวนวิธีไปถึงคะแนนที่กำหนดในเมทริกซ์คือ: 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
แนวทางที่ใช้ในโปรแกรมด้านล่าง
ในแนวทางนี้ เราจะใช้ dynamic programming เพื่อแก้ปัญหา เราจะใช้อาร์เรย์สองอาร์เรย์ arr[row][col][size] และ check[row][col][size] อาร์เรย์ check จะทำเครื่องหมายเซลล์ของ matrix[][] ว่าเยี่ยมชมแล้วเป็น true อาร์เรย์ arr[][][] ใช้เก็บจำนวนวิธีไปถึงเซลล์เฉพาะจาก matrix[0][0] เราจะคำนวณวิธีแบบเรียกซ้ำ
- รับอาร์เรย์ 2D matrix สำหรับเก็บตัวเลข
- รับตัวแปร score เป็นอินพุต
- รับอาร์เรย์สองอาร์เรย์ 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
