Ruudukko

#include <iostream>
#include <vector>
 
// Array to map out how many routes go out of each value and the value itself
// (paths from (mod 10^9 + 7, val)
std::vector<std::pair<uint64_t, int>> g_Map;
int g_LowestValue = 1000 * 1000 + 1;
int n = 0;
 
constexpr uint64_t c_ModVal = 1000000007;
 
// Fixed recursion
inline uint64_t GetRouteCount(int x, int y)
{
    auto& pair = g_Map[y * n + x];
 
    if(pair.first != 0)
        return pair.first;
 
    if(pair.second == g_LowestValue)
        return 0;
 
    // Check DOWN
    for(int i = y + 1; i < n; i++)
        if(g_Map[i * n + x].second < pair.second)
            pair.first += g_Map[i * n + x].first + 1;
 
    // Check UP
    for(int i = y - 1; i > -1; i--)
        if(g_Map[i * n + x].second < pair.second)
            pair.first += g_Map[i * n + x].first + 1;
 
    // Check RIGHT
    for(int i = x + 1; i < n; i++)
        if(g_Map[y * n + i].second < pair.second)
            pair.first += g_Map[y * n + i].first + 1;
 
    // Check LEFT
    for(int i = x - 1; i > -1; i--)
        if(g_Map[y * n + i].second < pair.second)
            pair.first += g_Map[y * n + i].first + 1;
 
    pair.first = pair.first % c_ModVal;
 
    return pair.first;
}
 
int main()
{
    std::cin >> n;
 
    g_Map.resize(n * n);
 
    std::vector<std::vector<std::pair<int, int>>> sortedValueCords;
    // Worst case
    sortedValueCords.resize(n * n);
 
    for(int y = 0; y < n; y++)
    {
        for(int x = 0; x < n; x++)
        {
            int val = 0;
            std::cin >> val;
 
            if(val < g_LowestValue)
                g_LowestValue = val;
 
            g_Map[y * n + x] = {0, val};
            sortedValueCords[val - 1].emplace_back(x, y);
        }
    }
 
    // Get all route values
    uint64_t routeTotal = 0;
 
    for(auto& vec : sortedValueCords)
        for(auto& c : vec)
            routeTotal += GetRouteCount(c.first, c.second);
 
    std::cout << (routeTotal + n * n) % c_ModVal << "\n";
}

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