比赛 |
SYOI2022 Round2 |
评测结果 |
RRRRRRRRRRR |
题目名称 |
方格取数问题 |
最终得分 |
0 |
用户昵称 |
HeSn |
运行时间 |
0.005 s |
代码语言 |
C++ |
内存使用 |
5.75 MiB |
提交时间 |
2022-06-15 21:01:11 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n, m, a[50][50], tx[4] = {0, 0, -1, 1}, ty[5] = {-1, 1, 0, 0}, ans = 0;
bool ok[50][50] = {0};
int dfs(int x, int y, int s) {
if(x > n || y > m) {
return 0;
}
if(x == n && y == m) {
ans = max(s, ans);
return 0;
}
for(int i = 0; i <= 3; i ++) {
if(ok[x + tx[i]][y + ty[i]] == 1) {
if(y == m) {
dfs(x + 1, 1, s);
return 0;
}
dfs(x, y + 1, s);
return 0;
}
}
if(y == m) {
ok[x][y] = 1;
dfs(x + 1, 1, s + a[x][y]);
ok[x][y] = 0;
dfs(x + 1, 1, s);
return 0;
}
ok[x][y] = 1;
dfs(x, y + 1, s + a[x][y]);
ok[x][y] = 0;
dfs(x, y + 1, s);
return 0;
}
int main() {
// freopen("grid.in", "r", stdin);
// freopen("grid.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
cin >> a[i][j];
}
}
dfs(1, 1, 0);
cout << ans << endl;
return 0;
}