Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> C++

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

Nhiệm vụ: tìm giá trị nguyên lớn nhất có thể đạt được khi đi từ góc trên trái [0][0] đến góc dưới phải [n-1][n-1] của ma trận vuông nhị phân. Chỉ được đi phải ([i][j+1]) hoặc xuống ([i+1][j]). Giá trị nguyên tính từ các bit trên đường đi.

Ví dụ 1

Đầu vào** –

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

Đầu ra** – 127

Giải thích** – Đường đi: [0,0]→[0,1]→[0,2]→[1,2]→[2,2]→[3,2]→[3,3]. Các bit = 1,1,1,1,1,1,1. Giá trị = Σ 2ⁱ (i=0..6) = 127.

Ví dụ 2

Đầu vào** –

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

Đầu ra** – 109

Phương pháp (Đệ quy)

  • Đệ quy từ (0,0) với tham số pw (lũy thừa 2).
  • Tại mỗi ô: nếu ngoài ma trận → trả 0.
  • Đệ quy sang phải và xuống, lấy max.
  • Nếu ô hiện tại = 1: trả 2^pw + max(phải, xuống); ngược lại trả max.

Ví dụ

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

#define side 4

int Max(int m[][side], int i, int j, int pw) {
    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;
}

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;
}

Đầu ra

127