Ruudukko

use std::io::stdin;

const MODULUS: u64 = 10_u64.pow(9) + 7;
const DEFAULT_SUM: u64 = u64::MAX;

struct Grid {
    n: u32,
    data: Vec<(u32, u64)>,
}

impl Grid {
    fn value(&self, x: u32, y: u32) -> Option<u32> {
        self.data.get((x + self.n * y) as usize).map(|(value, _)| *value)
    }

    fn sum(&mut self, x: u32, y: u32) -> Option<&mut u64> {
        self.data.get_mut((x + self.n * y) as usize).map(|(_, sum)| sum)
    }

    fn possible_paths(&mut self, x: u32, y: u32) -> Option<u64> {
        let sum = self.sum(x, y)?;
        if *sum != DEFAULT_SUM {
            Some(*sum)
        } else {
            let this_value = self.value(x, y)?;
            let mut sum: u64 = 1;
            if this_value == 1 {
                return Some(1);
            }
            for check_y in 0..self.n {
                if self.value(x, check_y)? < this_value {
                    sum += self.possible_paths(x, check_y)?;
                }
            }
            for check_x in 0..self.n {
                if self.value(check_x, y)? < this_value {
                    sum += self.possible_paths(check_x, y)?;
                }
            }

            sum %= MODULUS;
            *self.sum(x, y)? = sum;
            Some(sum)
        }
    }
}

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let n: u32 = buf.trim().parse().unwrap();

    let mut grid = Grid {
        n,
        data: Vec::with_capacity((n * n) as usize),
    };

    for _ in 0..n {
        buf.clear();
        stdin().read_line(&mut buf).unwrap();

        for value in buf.split_whitespace() {
            let value: u32 = value.parse().unwrap();
            grid.data.push((value, DEFAULT_SUM));
        }
    }

    let mut sum: u64 = 0;
    for x in 0..n {
        for y in 0..n {
            sum += grid.possible_paths(x, y).unwrap();
        }
    }

    println!("{}", sum % MODULUS);
}

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