深搜专题9：取数游戏

输入描述

第一行有一个正整数 T，表示了有 T 组数据。

对于每一组数据，第一行有两个正整数 N 和 M，表示了数字矩阵为 N 行 M 列。

接下来 N 行，每行 M 个非负整数，描述了这个数字矩阵。

• 对于20%的数据，1≤N,M≤3；
• 对于40%的数据，1≤N,M≤4；
• 对于60%的数据，1≤N,M≤5；
• 对于100%的数据，1≤N,M≤6，1≤T≤20。

输出描述

共 T 行，每行一个非负整数，输出所求得的答案。

用例输入 1 

3
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1

用例输出 1 

271
172
99

类似宽搜的题目（毕竟是兄弟嘛！）

#include <bits/stdc++.h>
using namespace std;
int dir[9][2]={{1,0},{-1,0},{0,0},{1,1},{-1,1},{0,1},{1,-1},{-1,-1},{0,-1}},vis[20][20],a[20][20],n,m,t,mx=-1,sum;
void ck(int x,int y){
    for(int i=0;i<9;i++){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        vis[tx][ty]++;//标记
    }
}
void ck1(int x,int y){
    for(int i=0;i<9;i++){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        vis[tx][ty]--;//回溯
    }
}
void dfs(int x,int y){
    for(int i=x;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!vis[i][j]){
                ck(i,j);//标记
            	sum+=a[i][j];累加此位置的值
                mx=max(sum,mx);
                dfs(i,j);
                ck1(i,j);
                sum-=a[i][j];//回溯
            }
            
        }
    }
}
int main(){
    cin>>t;
    while(t--){
        sum=0,mx=-1;
        memset(vis,0,sizeof(vis));//每轮的重置
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
            }
        }
        dfs(1,1);
    	cout<<mx<<endl;
    }
    return 0;
}