题解 | 取数游戏

#include <iostream>
using namespace std;
#include<vector>
int maxSum;
int row,col;
vector<vector<int>> grid;
vector<vector<bool>> used;
void backtracking(int pos,int currentSum){//pos指位置，将二维数组拉长成一维；currentSum指现在的和
    if(pos == row*col){//到最后一个位置
        maxSum = max(maxSum,currentSum);
        return;
    }
    int i = pos / col;
    int j = pos % col;//一维变二维

    backtracking(pos+1, currentSum);//不选择当前的数字
    //选择当前数字
    vector<pair<int,int>> directions = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};//需要从八个方向判断
    if(!used[i][j]){
        bool canSelect = true;//标记当前元素是否能被选择
        for(auto dir:directions){
            int newi = i+dir.first;
            int newj = j+dir.second;
            if(newi >= 0 && newi < row && newj >=0 && newj < col){//判断元素是否在矩阵范围内且没有被访问
                if(used[newi][newj]){
                    canSelect = false;
                    break;
                }
            }
        }
        if(canSelect){
            used[i][j] = true;
            backtracking(pos+1, currentSum+grid[i][j]);//遍历下一个位置，且当前和加上当前元素
            used[i][j] = false;//回溯，撤销节点
        }
    }
}
int main() {
    int T;
    cin >> T;
    while(T--){
        cin >> row >> col;
        grid.assign(row,vector<int>(col));
        used.assign(row,vector<bool>(col,false));
        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
                cin >> grid[i][j];
        maxSum = 0;
        backtracking(0,0);
        cout << maxSum << endl;
    }
    return 0;
}