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

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

ตัวอย่าง

อินพุต

col = 2; row = 4

ผลลัพธ์

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

คำอธิบาย

วิธีที่เราสามารถเข้าถึงได้จากเซลล์ 0,0 ถึง 2,4 แสดงไว้ -

อินพุต

col = 4; row = 3

ผลลัพธ์

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

คำอธิบาย

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).

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

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

• นำแถวจำนวนเต็ม col สำหรับมิติข้อมูลเมทริกซ์

• ฟังก์ชัน way_traverse_matrix(แถว int, int col) ใช้มิติข้อมูลและคืนค่าจำนวนวิธีในการสำรวจเมทริกซ์

• สำหรับ row==1 ให้คืนค่า 1

• สำหรับ col==1 ให้คืนค่า 1

• อย่างอื่นคำนวณวิธีโดยใช้การเรียกซ้ำ way_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;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

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