Skip to main content

rustgym/leetcode/
_835_image_overlap.rs

1struct Solution;
2
3impl Solution {
4    fn largest_overlap(a: Vec<Vec<i32>>, b: Vec<Vec<i32>>) -> i32 {
5        let n = a.len();
6        let mut res = 0;
7        for i in 0..n {
8            for j in 0..n {
9                res = res.max(Self::translate(i, j, &a, &b, n));
10                res = res.max(Self::translate(i, j, &b, &a, n));
11            }
12        }
13        res
14    }
15
16    fn translate(x: usize, y: usize, a: &[Vec<i32>], b: &[Vec<i32>], n: usize) -> i32 {
17        let mut res = 0;
18        for i in 0..n {
19            for j in 0..n {
20                if i + x < n && j + y < n {
21                    res += a[i + x][j + y] * b[i][j];
22                }
23            }
24        }
25        res
26    }
27}
28
29#[test]
30fn test() {
31    let a = vec_vec_i32![[1, 1, 0], [0, 1, 0], [0, 1, 0]];
32    let b = vec_vec_i32![[0, 0, 0], [0, 1, 1], [0, 0, 1]];
33    let res = 3;
34    assert_eq!(Solution::largest_overlap(a, b), res);
35}