题解 | 取数游戏

#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;
// 一行最多6个，那么使用8位数据即可完成一行的比较，速度快很多倍
// 把不可拿取的位置用1标记，然后一次与即可
bool IsEnable(const vector<int8_t>& flags, int y, int x, int m) {
	int8_t pFlag = int8_t(1) << (m-1-x);
	auto flag = flags[y];
	flag >>= 1;
	if(y > 0) {
		auto uFlag = flags[y-1];
		flag |= uFlag | uFlag << 1 | uFlag >> 1;
	}
	if(y + 1< flags.size()) {
		auto dFlag = flags[y+1];
		flag |= dFlag | dFlag << 1 | dFlag >> 1;
	}
	if(flag & pFlag) {
		return false;
	} else {
		return true;
	}
}
int GetSum(const vector<int8_t>& flags, int n, int m, const vector<vector<int>>& data) {
	int v = 0;
	for(auto i = 0; i < n; i++) {
		for(auto j = 0; j < m; j++) {
			if(flags[i]&(1<<(m-1-j))) {
				v += data[i][j];
			}
		}
	}
	return v;
}
int vMax = 0;
void Dfs(vector<int8_t>& flags, int n, int m, int i,const vector<vector<int>>& data) {
	if(i == n*m) {
		auto sum = GetSum(flags, n, m, data);
		vMax = max(sum, vMax);
		return;
	}
	auto x = i%m;
	auto y = i/m;
	if(IsEnable(flags, y, x, m)) {
		flags[y] |= 1 << (m-1-x);
		Dfs(flags, n, m, i+1, data);
		flags[y] &= ~(1<<(m-1-x));
	}
	Dfs(flags, n, m, i+1, data);
}
int main() {
    int t;
	cin >> t;
    while(t--) {
		int n, m;
		cin >> n >> m;
		vector<vector<int>> data(n, vector<int>(m));
		for(auto& vec : data) {
			for(auto& v : vec) {
				cin >> v;
			}
		}
		vector<int8_t> flags(n);
		vMax = 0;
		Dfs(flags, n, m, 0, data);
		cout << vMax << endl;
	}
}
// 64 位输出请用 printf("%lld")