[Rust] DP & Mask runs in 88ms
Realizing m <= 5 is crucial. It is possible to enuemrate all valid color permutation in a column and build dp based on it.\n\nuse std::collections::HashMap;\n\n
Realizing m <= 5 is crucial. It is possible to enuemrate all valid color permutation in a column and build dp based on it.\n```\nuse std::collections::HashMap;\n\nconst MOD: i32 = 1000_000_007;\nimpl Solution {\n    pub fn color_the_grid(m: i32, n: i32) -> i32 {\n        let mask = |mut x: usize| -> Vec<usize> {\n            let mut res = vec![];\n            for _ in 0..m {\n                res.push(x % 3);\n                x /= 3;\n            }\n            res\n        };\n        let mut candidate = vec![];\n        let m = m as usize;\n        let n = n as usize;\n        \'outer: for x in 0usize..(3usize.pow(m as u32)) {\n            let mut cur = mask(x);\n            for w in cur.windows(2) {\n                if w[0] == w[1] {\n                    continue \'outer;\n                }\n            }\n            candidate.push(x);\n        }\n        let mut nxt: HashMap<usize, Vec<usize>> = HashMap::new();\n        for cur in candidate.iter() {\n            for next_cur in candidate.iter() {\n                let c = mask(*cur);\n                let nc = mask(*next_cur);\n                if c.iter().zip(nc.iter()).all(|x| x.0 != x.1) {\n                    nxt.entry(*cur).or_default().push(*next_cur);\n                }\n            }\n        }\n        let mut dp: HashMap<usize, i32> = HashMap::new();\n        for i in candidate.iter() {\n            dp.insert(*i, 1);\n        }\n        for _ in 1..n {\n            let mut ndp: HashMap<usize, i32> = HashMap::new();\n            for (k, v) in dp.iter() {\n                for next in nxt[k].iter() {\n                    if let Some(value) = ndp.get_mut(next) {\n                        *value = (*value + *v) % MOD;\n                    } else {\n                        ndp.insert(*next, *v);\n                    }\n                }\n            }\n            dp = ndp;\n        }\n        let mut res = 0;\n        for v in dp.values() {\n            res = (res + *v) % MOD;\n        }\n        res\n    }\n}\n\n```
[]