นับจำนวนวิธีเดินทางในเมทริกซ์ด้วย C++

ได้รับเมทริกซ์ 2 มิติ ขนาด row × col เป้าหมายคือนับจำนวนวิธีที่สามารถเดินทางจากเซลล์ (0,0) ไปยังเซลล์ (row, col) โดยใช้การเคลื่อนที่ไปขวา (right) และลง (down) เท่านั้น คือ ขั้นแรกจาก (0,0) ไป (0,1) (ลง) หรือ (1,0) (ขวา) ไม่ใช่ (1,1) (เฉียง)

ตัวอย่าง

Input

col = 2; row = 4

Output

Count of number of ways to traverse a Matrix are: 4

Explanation

วิธีการไปจากเซลล์ (0,0) ถึง (2,4) แสดงในรูปด้านล่าง

Input

col = 4; row = 3

Output

Count of number of ways to traverse a Matrix are: 10

Explanation

We will reduce the problem into smaller recursions. Count ways for col=3, row=2, then for col=2, row=1 ... For col=1 or row=1 the answer will be 1. (only right or only down move).

วิธีการที่ใช้ในโปรแกรม

วิธีนี้ใช้วิธีการเรียกซ้ำ (recursion) ในที่สุดสำหรับ row หรือ col เป็น 1 จะมีวิธีเดียวคือ เดินตรงไปขวาหรือลงอย่างเดียว นี่คือเงื่อนไขหยุดของ recursion

• รับจำนวนเต็ม row, col สำหรับขนาดเมทริกซ์
• ฟังก์ชัน ways_traverse_matrix(int row, int col) คืนค่าจำนวนวิธีเดินทางในเมทริกซ์
• ถ้า row==1 คืนค่า 1
• ถ้า col==1 คืนค่า 1
• มิฉะนั้น คำนวณวิธีด้วย recursion: ways_traverse_matrix(temp_1, col) + ways_traverse_matrix(row, temp_2)
• โดย temp_1 = หมายเลขแถวก่อนหน้า และ temp_2 = หมายเลขคอลัมน์ก่อนหน้า
• ในที่สุดจะได้จำนวนวิธีทั้งหมด

ตัวอย่างโค้ด

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

int ways_traverse_matrix(int row, int col){
    if (row == 1){
        return 1;
    }
    else if(col == 1){
        return 1;
    } else {
        int temp_1 = row - 1;
        int temp_2 = col - 1;
        return ways_traverse_matrix(temp_1, col) + ways_traverse_matrix(row, temp_2);
    }
}

int main(){
    int col = 2;
    int row = 2;
    cout << "Count the number of ways to traverse a Matrix are: " << ways_traverse_matrix(row, col);
    return 0;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count the number of ways to traverse a Matrix are: 2