题目描述
给你一个正方形字符数组 board ，你从数组最右下方的字符 'S' 出发。
你的目标是到达数组最左上角的字符 'E' ，数组剩余的部分为数字字符 1, 2, ..., 9 或者障碍 'X'。在每一步移动中，你可以向上、向左或者左上方移动，可以移动的前提是到达的格子没有障碍。
一条路径的 「得分」 定义为：路径上所有数字的和。
请你返回一个列表，包含两个整数：第一个整数是 「得分」 的最大值，第二个整数是得到最大得分的方案数，请把结果对 10^9 + 7 取余。
如果没有任何路径可以到达终点，请返回 [0, 0] 。
示例 1：
输入：board = ["E23","2X2","12S"]
输出：[7,1]
示例 2：
输入：board = ["E12","1X1","21S"]
输出：[4,2]
示例 3：
输入：board = ["E11","XXX","11S"]
输出：[0,0]
提示：
2 <= board.length == board[i].length <= 100
解法
方法一：动态规划
我们定义 $f[i][j]$ 表示从起点 $(n - 1, n - 1)$ 到达 $(i, j)$ 的最大得分，定义 $g[i][j]$ 表示从起点 $(n - 1, n - 1)$ 到达 $(i, j)$ 的最大得分的方案数。初始时 $f[n - 1][n - 1] = 0$，并且 $g[n - 1][n - 1] = 1$。其它位置的 $f[i][j]$ 均为 $-1$，而 $g[i][j]$ 均为 $0$。
对于当前位置 $(i, j)$，它可以由 $(i + 1, j)$, $(i, j + 1)$, $(i + 1, j + 1)$ 三个位置转移而来，因此我们可以枚举这三个位置，更新 $f[i][j]$ 和 $g[i][j]$ 的值。如果当前位置 $(i, j)$ 有障碍，或者当前位置是起点，或者其它位置越界，则不进行更新。否则，如果其它位置 $(x, y)$ 满足 $f[x][y] \gt f[i][j]$，那么我们更新 $f[i][j] = f[x][y]$，并且 $g[i][j] = g[x][y]$。如果 $f[x][y] = f[i][j]$，那么我们更新 $g[i][j] = g[i][j] + g[x][y]$。最后，如果当前位置 $(i, j)$ 可达并且是数字，我们更新 $f[i][j] = f[i][j] + board[i][j]$。
最后，如果 $f[0][0] \lt 0$，说明没有路径可以到达终点，返回 $[0, 0]$。否则，返回 $[f[0][0], g[0][0]]$。注意，返回结果需要对 $10^9 + 7$ 取余。
时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 是数组的边长。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution:
def pathsWithMaxScore(self, board: List[str]) -> List[int]:
def update(i, j, x, y):
if x >= n or y >= n or f[x][y] == -1 or board[i][j] in "XS":
return
if f[x][y] > f[i][j]:
f[i][j] = f[x][y]
g[i][j] = g[x][y]
elif f[x][y] == f[i][j]:
g[i][j] += g[x][y]
n = len(board)
f = [[-1] * n for _ in range(n)]
g = [[0] * n for _ in range(n)]
f[-1][-1], g[-1][-1] = 0, 1
for i in range(n - 1, -1, -1):
for j in range(n - 1, -1, -1):
update(i, j, i + 1, j)
update(i, j, i, j + 1)
update(i, j, i + 1, j + 1)
if f[i][j] != -1 and board[i][j].isdigit():
f[i][j] += int(board[i][j])
mod = 10**9 + 7
return [0, 0] if f[0][0] == -1 else [f[0][0], g[0][0] % mod]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 | class Solution {
private List<String> board;
private int n;
private int[][] f;
private int[][] g;
private final int mod = (int) 1e9 + 7;
public int[] pathsWithMaxScore(List<String> board) {
n = board.size();
this.board = board;
f = new int[n][n];
g = new int[n][n];
for (var e : f) {
Arrays.fill(e, -1);
}
f[n - 1][n - 1] = 0;
g[n - 1][n - 1] = 1;
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
update(i, j, i + 1, j);
update(i, j, i, j + 1);
update(i, j, i + 1, j + 1);
if (f[i][j] != -1) {
char c = board.get(i).charAt(j);
if (c >= '0' && c <= '9') {
f[i][j] += (c - '0');
}
}
}
}
int[] ans = new int[2];
if (f[0][0] != -1) {
ans[0] = f[0][0];
ans[1] = g[0][0];
}
return ans;
}
private void update(int i, int j, int x, int y) {
if (x >= n || y >= n || f[x][y] == -1 || board.get(i).charAt(j) == 'X'
|| board.get(i).charAt(j) == 'S') {
return;
}
if (f[x][y] > f[i][j]) {
f[i][j] = f[x][y];
g[i][j] = g[x][y];
} else if (f[x][y] == f[i][j]) {
g[i][j] = (g[i][j] + g[x][y]) % mod;
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44 | class Solution {
public:
vector<int> pathsWithMaxScore(vector<string>& board) {
int n = board.size();
const int mod = 1e9 + 7;
int f[n][n];
int g[n][n];
memset(f, -1, sizeof(f));
memset(g, 0, sizeof(g));
f[n - 1][n - 1] = 0;
g[n - 1][n - 1] = 1;
auto update = [&](int i, int j, int x, int y) {
if (x >= n || y >= n || f[x][y] == -1 || board[i][j] == 'X' || board[i][j] == 'S') {
return;
}
if (f[x][y] > f[i][j]) {
f[i][j] = f[x][y];
g[i][j] = g[x][y];
} else if (f[x][y] == f[i][j]) {
g[i][j] = (g[i][j] + g[x][y]) % mod;
}
};
for (int i = n - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
update(i, j, i + 1, j);
update(i, j, i, j + 1);
update(i, j, i + 1, j + 1);
if (f[i][j] != -1) {
if (board[i][j] >= '0' && board[i][j] <= '9') {
f[i][j] += (board[i][j] - '0');
}
}
}
}
vector<int> ans(2);
if (f[0][0] != -1) {
ans[0] = f[0][0];
ans[1] = g[0][0];
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 | func pathsWithMaxScore(board []string) []int {
n := len(board)
f := make([][]int, n)
g := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
g[i] = make([]int, n)
for j := range f[i] {
f[i][j] = -1
}
}
f[n-1][n-1] = 0
g[n-1][n-1] = 1
const mod = 1e9 + 7
update := func(i, j, x, y int) {
if x >= n || y >= n || f[x][y] == -1 || board[i][j] == 'X' || board[i][j] == 'S' {
return
}
if f[x][y] > f[i][j] {
f[i][j] = f[x][y]
g[i][j] = g[x][y]
} else if f[x][y] == f[i][j] {
g[i][j] = (g[i][j] + g[x][y]) % mod
}
}
for i := n - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
update(i, j, i+1, j)
update(i, j, i, j+1)
update(i, j, i+1, j+1)
if f[i][j] != -1 && board[i][j] >= '0' && board[i][j] <= '9' {
f[i][j] += int(board[i][j] - '0')
}
}
}
ans := make([]int, 2)
if f[0][0] != -1 {
ans[0], ans[1] = f[0][0], g[0][0]
}
return ans
}
|