Robot Coin Collection

main.cpp

#include <iostream>
#include <bitset>
#include <vector>
#include <cassert>

using namespace std;


template<size_t bitset_size>
int robot_coin_collection(vector<bitset<bitset_size>> &coin_matrix) {
    vector<vector<int>> result_matrix(coin_matrix.size(), vector<int>(bitset_size));
    result_matrix[0][0] = coin_matrix[0][bitset_size - 1];

    for (int j = 1; j < bitset_size; ++j)
        result_matrix[0][j] = result_matrix[0][j - 1]
                              + coin_matrix[0][(bitset_size - 1) - j];

    for (int i = 1; i < coin_matrix.size(); ++i) {
        result_matrix[i][0] = result_matrix[i - 1][0]
                              + coin_matrix[i][bitset_size - 1];

        for (int j = 1; j < bitset_size; ++j) {
            result_matrix[i][j] = max(result_matrix[i - 1][j], result_matrix[i][j - 1])
                                  + coin_matrix[i][(bitset_size - 1) - j];
        }
    }

    return result_matrix.back().back();
}


int main() {
    {
        vector<bitset<6>> coin_matrix
                {
                        {0b0100},
                        {0b0101}
                };

        assert(robot_coin_collection(coin_matrix) == 3);
    }

    {
        vector<bitset<6>> coin_matrix
                {
                        {0b0010},
                        {0b0101}
                };

        assert(robot_coin_collection(coin_matrix) == 2);
    }


    {
        vector<bitset<6>> coin_matrix
                {
                        {0b000010},
                        {0b010100},
                        {0b000101},
                        {0b001001},
                        {0b100010}
                };

        assert(robot_coin_collection(coin_matrix) == 5);
    }


    return 0;
}