Ruudukko

use std::{io::stdin, collections::HashMap};

struct Grid {
    n: u32,
    data: Vec<u32>,
    path_cache: HashMap<u64, u64>,
}

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

    fn possible_paths(&mut self, x: u32, y: u32) -> Option<u64> {
        let key = (x as u64) << 32 | y as u64;
        if let Some(&s) = self.path_cache.get(&key) {
            Some(s)
        } else {
            let this_value = self.get(x, y)?;
            if this_value == 1 {
                return Some(1);
            }
            let mut sum: u64 = 1;
            for check_y in 0..self.n {
                if self.get(x, check_y)? < this_value {
                    sum += self.possible_paths(x, check_y)?;
                }
            }
            for check_x in 0..self.n {
                if self.get(check_x, y)? < this_value {
                    sum += self.possible_paths(check_x, y)?;
                }
            }

            self.path_cache.insert(key, 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),
        path_cache: HashMap::new(),
    };

    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);
        }
    }

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

    println!("{}", sum % (10_u64.pow(10) + 7));
}

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: WRONG ANSWER

Test 6

Group: 2, 3

Verdict: WRONG ANSWER

Test 7

Group: 3

Verdict: ACCEPTED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED