# 2023-04-07：求解矩阵得分点问题！——本文探讨蚂蚁金服算法面试题，介绍两种解决方案：递归和数学公式

2023-04-07：得分的定义 :

1 0
0 1 可以得1分

0 1
1 0 可以得1分

0 1 0
1 0 1

1 <= N、M <= 10^9。

# rust完整代码如下：

``````fn score1(n: i32, m: i32) -> i32 {
if n < 2 || m < 2 {
return 0;
}
let mut matrix = vec![vec![0; m as usize]; n as usize];
process(&mut matrix, 0, 0, n, m)
}

fn process(matrix: &mut Vec<Vec<i32>>, i: i32, j: i32, n: i32, m: i32) -> i32 {
if i == n {
let mut score = 0;
for r in 1..n {
for c in 1..m {
if check(&matrix, r, c) {
score += 1;
}
}
}
return score;
}
if j == m {
return process(matrix, i + 1, 0, n, m);
}
let mut score = 0;
matrix[i as usize][j as usize] = 1;
score += process(matrix, i, j + 1, n, m);
matrix[i as usize][j as usize] = 0;
score += process(matrix, i, j + 1, n, m);
score
}

fn check(m: &Vec<Vec<i32>>, r: i32, c: i32) -> bool {
(m[(r - 1) as usize][(c - 1) as usize] == 0
&& m[r as usize][(c - 1) as usize] == 1
&& m[(r - 1) as usize][c as usize] == 1
&& m[r as usize][c as usize] == 0)
|| (m[(r - 1) as usize][(c - 1) as usize] == 1
&& m[r as usize][(c - 1) as usize] == 0
&& m[(r - 1) as usize][c as usize] == 0
&& m[r as usize][c as usize] == 1)
}

fn score2(n: i32, m: i32) -> i32 {
if n < 2 || m < 2 {
return 0;
}
(n * m - m - n + 1) * (1 << (n * m - 3))
}

fn main() {
let n = 3;
let m = 4;
println!("{}", score1(n, m));
println!("{}", score2(n, m));
}
``````

(=￣ω￣=)··· 暂无内容！

337

14

27

12