Ruudukko

# returns array of num arrays
def get_input():
    height = int(input())
    lines = []  # of int[]
    line = []   # of str
    for _ in range(height):
        line = input().split()
        lines.append([eval(num) for num in line])
    return (height, lines)


# constants
(HEIGHT, LINES) = get_input()
MAX_ARRAY_INDEX = HEIGHT - 1

# global memo item
memo = dict()


# str in format "row,col" and int
# uses recursion
def count_possible_moves(square_coordinate : str, square_num : int) -> int:
    if (square_num < 2): return 0
    move_count = memo.get(square_coordinate, -1)
    if (move_count >= 0): 
        return move_count

    # row col combo not in memo
    counter = 0
    separator_index = str(square_coordinate).find(",")
    row = int(square_coordinate[:separator_index])
    col = int(square_coordinate[separator_index + 1:])

    # loop right
    right_col = col + 1
    while (right_col <= MAX_ARRAY_INDEX):
        if (square_num > LINES[row][right_col]):
            counter += 1
            counter += count_possible_moves(f"{row},{right_col}", LINES[row][right_col])
        right_col += 1

    # loop left
    left_col = col - 1
    while (left_col >= 0):
        if (square_num > LINES[row][left_col]):
            counter += 1
            counter += count_possible_moves(f"{row},{left_col}", LINES[row][left_col])
        left_col -= 1

    # loop down
    down_row = row + 1
    while (down_row <= MAX_ARRAY_INDEX):
        if (square_num > LINES[down_row][col]):
            counter += 1
            counter += count_possible_moves(f"{down_row},{col}", LINES[down_row][col])
        down_row += 1

    # loop up 
    up_row = row - 1
    while (up_row >= 0):
        if (square_num > LINES[up_row][col]):
            counter += 1
            counter += count_possible_moves(f"{up_row},{col}", LINES[up_row][col])
        up_row -= 1

    memo[square_coordinate] = counter
    return counter


def main():
    counter = 0
    # loop throught every square
    for i in range(len(LINES)):
        for j in range(len(LINES[i])):
            count = count_possible_moves(f"{i},{j}", LINES[i][j])
            # add current square in count
            counter += count + 1 
    # print result
    print(counter % ((10**9)+9)) 

main()

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: TIME LIMIT EXCEEDED

Test 6

Group: 2, 3

Verdict: WRONG ANSWER

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED