比赛 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;
}