Ruudukko

#include <iostream>
int n;
int visited = 0;
int sum = 0;
int arr[1001][1001];
int gps[1001][1001]={0};

int route(int x, int y){
    if (gps[x][y]!=0)
        return gps[x][y];
    if (arr[x][y]==1){
        gps[x][y] = 1;
        visited++;
        sum++;
        return 1;
    }
    int routes = 1;
    for (int i=0;i<n;i++){
        if (arr[x][i]<arr[x][y])
            routes += route(x,i);
        if (routes>1000000007)
            routes %= 1000000007;
        if (arr[i][y]<arr[x][y])
            routes += route(i,y);
        if (routes>1000000007)
            routes %= 1000000007;
    }
    gps[x][y] = routes;
    visited++;
    sum += routes;
    if (sum>=1000000007)
        sum %= 1000000007;
    return routes;
}

int main(){
    std::cin.sync_with_stdio(false);
    std::cin >> n;
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            std::cin >> arr[i][j];
        }
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            route(i,j);
            if (visited==n*n)
                goto results;
        }
    }
    results:
    std::cout << sum << "\n";
    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: ACCEPTED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED