Đường dẫn giá trị thập phân lớn nhất trong ma trận nhị phân trong C ++

Nhiệm vụ được giao là tìm giá trị số nguyên lớn nhất có thể nhận được khi đi theo đường từ phần tử trên cùng bên trái đến phần tử dưới cùng bên phải của một mảng nhị phân vuông đã cho, nghĩa là bắt đầu từ chỉ mục [0] [0] đến chỉ mục [n - 1] [n - 1].

Trong khi che con đường, chúng ta chỉ có thể di chuyển sang phải ([i] [j + 1]) hoặc xuống dưới cùng ([i + 1] [j])

Giá trị số nguyên sẽ được tính toán bằng cách sử dụng các bit của đường dẫn được duyệt qua.

Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ -

Đầu vào

m = {
   {1, 1, 1, 1},
   {0, 0, 1, 0},
   {1, 0, 1, 1},
   {0, 1, 1, 1}
}

Đầu ra

Giải thích

Đường mà chúng tôi đã đi là:[0, 0] → [0, 1] → [0, 2] → [1, 2] → [2, 2] → [3, 2] → [3, 3]

Do đó giá trị thập phân trở thành =1 * (2 ⁰ ) + 1 * (2 ¹ ) + 1 * (2 ² ) + 1 * (2 ³ ) + 1 * (2 ⁴ ) + 1 * (2 ⁵ ) + 1 * (2 ⁶ )

=1 + 2 + 4 + 8 + 16 + 32 + 64

=127

Đầu vào

m = {
   {1, 0, 1, 1},
   {0, 0, 1, 0},
   {1, 0, 0, 1},
   {0, 1, 1, 1}
}

Đầu ra

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Trước tiên, hãy xác định kích thước cạnh của ma trận vuông ở trên cùng bằng cách sử dụng #define.
Trong hàm main (), tạo một mảng 2D int m [] [4] để lưu trữ ma trận và gọi Max (m, 0, 0, 0)
Trong hàm max () trước tiên hãy kiểm tra xem (i> =side || j> =side). Nếu vậy, điều đó có nghĩa là chúng ta đã ra khỏi ranh giới ma trận và trả về 0.
Tạo một biến mới int ans và đặt ans =max (Max (m, i, j + 1, pw + 1), Max (m, i + 1, j, pw + 1)).
Sau đó kiểm tra xem (m [i] [j] ==1). Nếu vậy, hãy trả về pow (2, pw) + ans.
Nếu không, chỉ cần trả về ans.

Ví dụ

#include<bits/stdc++.h>
using namespace std;
#define side 4
// pw is power of 2
int Max(int m[][side], int i, int j, int pw){
   // Out of boundary
   if (i >= side || j >= side )
      return 0;
   int ans = max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1));
   if (m[i][j] == 1)
      return pow(2, pw) + ans;
   else
      return ans;
}
//main function
int main(){
   int m[][4] = {{1, 1, 1, 1},{0, 0, 1, 0},{1, 0, 1, 1},{0, 1, 1, 1}};
   cout << Max(m, 0, 0, 0);
   return 0;
}