C++ - response is int%

Question

I decide 2D Dinamic Coding on C++, i'm decide task about count of ways to bottom-right field in table, and my program return %. Why? Program:

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int arr[n][m];

    for (int i = 0; i < n; i++) 
        arr[i][0] = 1;

    for (int i = 0; i < m; i++)
        arr[0][i] = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++)
            arr[i][j] = arr[i-1][j] + arr[i][j-1];
    }

    cout << arr[n-1][m-1];
}

I would like answer Request: 1 10 Response: 1

Please note, that this isn't [valid c++ code](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). Also you don't initialize every cell of the 2d array. — πάντα ῥεῖ, May 28 '22 at 08:17
`int arr[n][m]` (where `n` and `m` are values read at run time) is not valid C++. Unfortunately, some compilers support such a thing as a *non-standard* extension, which is a trap for novices using those compilers. Beyond that, your question is unclear. Voting to close accordingly. — Peter, May 28 '22 at 08:19
I'd recommend getting familiar with the regular and portable c++ containers like `std::vector` for using _"dinamic allocation"_. — πάντα ῥεῖ, May 28 '22 at 08:25

Ted Lyngmo · Accepted Answer · 2022-05-28T13:08:17.223

Your program has undefined behavior for any other sizes than n = 1 and m = 1 because you leave the non-standard VLA (variable length array) arr's positions outside arr[0][0] uninitialized and later read from those positions. If you want to continue using these non-standard VLA:s, you need to initialize them after constructing them. Example:

#include <cstring> // std::memset

    // ...
    int arr[n][m];
    std::memset(arr, 0, sizeof arr); // zero out the memory
    // ...

Another approach that would both make it initialized and be compliant with standard C++ would be to use std::vectors instead:

#include <vector>

    // ...
    std::vector<std::vector<int>> arr(n, std::vector<int>(m));
    // ...

A slightly more cumbersome approach is to store the data in a 1D vector inside a class and provide methods of accessing the data as if it was stored in a 2D matrix. A class letting you store arbitrary number of dimensions could look something like below:

#include <utility>
#include <vector>

template <class T, size_t Dim> // number of dimensions as a template parameter
class matrix {
public:
    template <class... Args>
    matrix(size_t s, Args&&... sizes)  // sizes of all dimensions
        : m_data(s * (... * sizes)),   // allocate the total amount of data
          m_sizes{s, static_cast<size_t>(sizes)...}, // store sizes
          m_muls{static_cast<size_t>(sizes)..., 1}   // and multipliers
    {
        static_assert(sizeof...(Args) + 1 == Dim);
        for (size_t i = Dim - 1; i--;)
            m_muls[i] *= m_muls[i + 1]; // calculate dimensional multipliers
    }

    template <size_t D> size_t size() const { return m_sizes[D]; }
    size_t size(size_t D) const { return m_sizes[D]; }

    // access the data using (y,z) instead of [y][x]
    template <class... Args>
    T& operator()(Args&&... indices) {
        static_assert(sizeof...(Args) == Dim);
        return op_impl(std::make_index_sequence<Dim>{}, indices...);
    }

private:
    template <std::size_t... I, class... Args>
    T& op_impl(std::index_sequence<I...>, Args&&... indices) {
        return m_data[(... + (indices * m_muls[I]))];
    }

    std::vector<T> m_data;
    size_t m_sizes[Dim];
    size_t m_muls[Dim];
};

With such a wrapper, you'd only need to change the implementation slightly:

#include <iostream>

int main() {
    int n, m;
    if(!(std::cin >> n >> m && n > 0 && m > 0)) return 1;

    matrix<int, 2> arr(n, m);

    for (int i = 0; i < arr.size<0>(); i++)
        arr(i, 0) = 1;

    for (int i = 0; i < arr.size<1>(); i++)
        arr(0, i) = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) 
            arr(i, j) = arr(i - 1, j) + arr(i, j - 1);
    }

    std::cout << arr(n - 1, m - 1) << '\n';
}

Your latter proposed approach provides a quite different (and usually less efficient) memory layout. Better use to have a single `std::vector` encapsulated in a class responsible to do the indexing math for 2D, 3D, ... nD. — πάντα ῥεῖ, May 28 '22 at 08:41
@πάνταῥεῖ I added a wrapper for nD too to make the answer a bit more complete. — Ted Lyngmo, May 28 '22 at 13:09

C++ - response is int%

1 Answers1