Ruudukko

// CPP program to count number
// of decreasing path in a matrix
//#include <bits/stdc++.h>
// using namespace std;
//#include <iostream>


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

#define MAX 1000

// Function that returns the number of
// decreasing paths from a cell(i, j)
int CountDecreasingPathsCell(int(&mat)[MAX][MAX], int(&dp)[MAX][MAX],
                                              int n, int x, int y, int (&delta)[4*MAX][2], int modulo_num)
{
    // checking if already calculated
    if (dp[x][y] != -1)
        return dp[x][y];
 
    // all possible paths
    //int delta[4][2] = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } };
    
    
    int newx, newy;
 
    // counts the total number of paths
    int ans = 1;

    
 
    // In all four allowed direction.
    for (int i = 0; i < 4*n; i++) {
 
        // new co-ordinates
        newx = x + delta[i][0];
        newy = y + delta[i][1];
 
        // Checking if not going out of matrix and next
        // cell value is less than current cell value.
        if (newx >= 0 && newx < n && newy >= 0
            && newy < n && mat[newx][newy] < mat[x][y]) {
            ans += CountDecreasingPathsCell(mat, dp, n, newx, newy, delta, modulo_num);
            if (ans >= modulo_num){
                ans = ans % modulo_num;
            }
        }
    }
    // function that returns the answer
    return dp[x][y] = ans;
}
 
// Function that counts the total
// decreasing path in the matrix
int countDecreasingPathsMatrix(int n,
                               int(&mat)[MAX][MAX], int(&delta)[4*MAX][2], int modulo_num)
{
    int dp[MAX][MAX];
 
    // Initialising dp[][] to -1.
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            dp[i][j] = -1;
        }
    }
 
    int sum = 0;


 
    // Calculating number of decreasing path from each cell.
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            sum += CountDecreasingPathsCell(mat, dp, n, i, j, delta, modulo_num);
            if (sum >= modulo_num){
                sum = sum % modulo_num;
            }
            //sum += CountDecreasingPathsCell(mat, dp, n, i, j) % modulo_num;
        }
    }
    return sum;
}





// Driver Code
int main()
{
    //int i = 1;
    int number_of_rows;
    cin >> number_of_rows; 
    //int input_row[number_of_rows] = {};
    int input_row1;
    //string replace_char = ",";


    //int mat[1000][1000];

    int modulo_num = pow(10, 9) + 7;

    //int j;

    int delta[4*MAX][2];
    int C = 0;
    for (int i = -number_of_rows; i<=number_of_rows; i++){
        if(i != 0){
            delta[C][0] = i;
            delta[C][1] = 0;
            C++;
        }
    }
    C++;
    for (int i = -number_of_rows; i<=number_of_rows; i++){
        if(i != 0){
            delta[C][0] = 0;
            delta[C][1] = i;
            C++;
        }
    }


    int my_array[MAX][MAX];

    //cout << number_of_rows << endl;

    for (int iii = 0; iii < number_of_rows; iii++)
    {
        for (int ii = 0; ii < number_of_rows; ii++)
        {
            cin >> input_row1;

            //input_row[ii] = input_row1;
            //cout << input_row1 << "its the input row" << endl;

            my_array[iii][ii] = input_row1;

            //char *modified_input = strtok(input_row, " ");
            //cout << modified_input << "its modified_input" << endl;
            //int number = stoi(modified_input);
            //cout << number << "its the number" << endl;
            //my_array[ii] = number;
            //cout << ii << "its the ii number" << endl;
            //cout << iii << "its the iii number----" << endl;

        }

        //my_array[iii] = input_row;
    }



    //int arrSize = sizeof(my_array)/sizeof(my_array[0]);
    //cout << arrSize << "its the length of arrSize" << endl;
    //cout << input_row[0] << "its the input_row---" << endl;
    //cout << input_row[1] << "its the input_row---" << endl;
    //cout << input_row[2] << "its the input_row---" << endl;

    //cout << my_array[0][0] << "its the my_array " << endl;
    //cout << my_array[1][1] << "its the my_array " << endl;

    //std::copy_n(std::istream_iterator<int>(std::cin), number_of_rows, my_array);

    //int mat[100][100] = { { 2, 1, 3 }, { 1, 1, 1 }, {9, 2, 7} };     // function call that returns the

    //cout << mat[50][0] << "its the mat print" << endl;
    //cout << modulo_num << "its the modulo_num" << endl;

    //int modulo_num = pow(10, 9)+7;


    int number_of_paths = countDecreasingPathsMatrix(number_of_rows, my_array, delta, modulo_num);
    cout << number_of_paths << endl;      // count of decreasing paths in a matrix
    return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: ACCEPTED

Test 6

Group: 2, 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED