Em muốn hỏi code bài qhd này ạ.
Cho 1 mảng n hàng, m cột. từ cột (i, j) có thể đi lên trên, xuống dưới hoặc sang phải. Với ô (i, j) chứ kí tự ‘.’ thể hiện rằng có thể đi qua, chứa kí tự ‘*’ thể hiện ô có vật cản không thể đi qua, chứa số nguyên x thuộc [1, 9] thể hiện ô đó chứ đồng tiền giá trị x. Biết rằng ô được xuất phát từ (n, 1) và phải đi tới ô(n, m), tìm đường đi tới ô (n, m) sao cho tổng giá trị tiền thu được là lớn nhất.
input: số nguyên n, m. n hàng tiếp theo chứa m kí tự
ouput: tổng số tiền thu được lớn nhất, nếu không thể đi in ra -1;
test mẫu:
input:
5 10
. . 3 . . . . . . .
. . . . . . . . . .
. . 7 . * * . . . .
. 9 * * . . . 1 . .
. . 8 . . 9 . . . .
ouput: 27
P/s: output của em ra là 26, code của em đây ạ
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
char a[1005][1005];
int dp[1005][1005];
bool check (char s)
{
if (s >= '0' && s <= '9')
return true;
return false;
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> a[i][j];
if (a[n - 1][1] == '*' && a[n][2] == '*')
{
cout << -1 << '\n';
return 0;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
if (check(a[i][j]))
dp[i][j] = max(dp[i - 1][j - 1], max(dp[i - 1][j], dp[i][j - 1])) + (a[i][j] - '0');
else if (a[i][j] == '.')
dp[i][j] = max(dp[i - 1][j - 1], max(dp[i - 1][j], dp[i][j - 1]));
else
dp[i][j] = 0;
}
cout << dp[n][m] << '\n';
}
kq bài là 27 nhưng code của em ra 26 ạ
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?