[洛谷]P1123 取数游戏

最近准备蓝桥杯 一直在练搜索和图论hhh

题意

给定$n\times m$的数字矩阵
可以取出若干数字
但是有限制 取出的两个数字不能在八联通方向上相邻

$$1\le N,M\le 6，1\le T\le 20$$

思路

遍历方式

这道题的dfs方式对我来说是第一次接触
学到很多

本题采取遍历矩阵中的行优先的方式
可以理解为把下面这段常见的双重循环遍历拆成dfs中的坐标一步一步加减

for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)

也就是对于每一行(每一个$x$)
先把这一行的每一列走完 (先$y$++)
然后再把$x$++

如何保证八联通内不相邻？

定义一个别样的$vis$数组 $int$ 类型
用来记录$(i,j)$这个点八联通范围内有多少个点被选过


如果vis[i][j]==0 对于这个点可以有选和不选两种操作

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define pii pair<int,int>
#define ar2 array<int,2>
#define ar3 array<int,3>
#define ar4 array<int,4>
#define endl '\n'
void cmax(int &a,int b){a=max(a,b);}
void cmin(int &a,int b){a=min(a,b);}
const int N=20,MOD=1e9+7,INF=0x3f3f3f3f,LINF=LLONG_MAX;
int dx[]={1,1,1,0,0,-1,-1,-1};
int dy[]={1,-1,0,1,-1,0,1,-1};

int n,m,g[N][N];
int vis[N][N];
int ans=0;

void dfs(int x,int y,int sum){
    if(y==m+1){
        cmax(ans,sum);
        dfs(x+1,1,sum);
        return;
    }
    if(x==n+1){
        cmax(ans,sum);
        return;
    }
    
    //不选
    dfs(x,y+1,sum);
    
    if(vis[x][y]==0) {
            
        //选
        // vis[x][y]=1;
        for(int i=0;i<8;i++){
            int tx=x+dx[i],ty=y+dy[i];
            if(tx<1||tx>n||ty<1||ty>m) continue;
            vis[tx][ty]++;
        }

        dfs(x,y+1,sum+g[x][y]);
        
        // vis[x][y]=0;
        for(int i=0;i<8;i++){
            int tx=x+dx[i],ty=y+dy[i];
            if(tx<1||tx>n||ty<1||ty>m) continue;
            vis[tx][ty]--;
        }
    }
}

void solve() {
    memset(vis,0,sizeof vis);
    memset(g,0,sizeof g);
    ans=0;

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
        }
    }
    
    dfs(1,1,0);
    cout<<ans<<endl;

}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t=1;
    cin>>t;
    while (t--) solve();

}

代码细节

• dfs中 在最前面判断完x和y之后
  不要单独判断vis[x][y]==1

if(vis[x][y]){
	dfs(x,y+1,sum);
	return;
}

要判断的话就要写成这样 里面会多一次dfs
然后在这个判断过后 再分类讨论选或不选
这样会多很多次递归 会tle

• 所以要写成上面code这样
• 先走不选这个dfs 因为无论这个点能不能选 不选这个选项肯定要走一次的
• 然后也不要判断vis[x][y]!=0 因为会多一次dfs
• 直接判断vis[x][y]==0 然后 后面写选这个点的情况

	//不选
    dfs(x,y+1,sum);
    
    if(vis[x][y]==0) {
            
        //选
        for(int i=0;i<8;i++){
            int tx=x+dx[i],ty=y+dy[i];
            if(tx<1||tx>n||ty<1||ty>m) continue;
            vis[tx][ty]++;
        }

        dfs(x,y+1,sum+g[x][y]);

        for(int i=0;i<8;i++){
            int tx=x+dx[i],ty=y+dy[i];
            if(tx<1||tx>n||ty<1||ty>m) continue;
            vis[tx][ty]--;
        }

这样就能减少递归次数
记得回溯

原来错的细节

• 我一开始把$(i,j)$选上后 就把这一块九个点的vis都记为true 然后在dfs中 如果vis[x][y]==1 就更新ans 然后return 并且写了一个check函数 检查这个点八联通范围内有没有vis为true的点 如果有就跳过这个点

• 这是完全错误的 因为一个点没选 但是它左边的点选了 这个点也会$vis==true$ 那么它右边这个点就会因为它的$vis==true$而被跳过

• 还有 碰到$vis[x][y]==1$时 不应该直接更新ans并且return 因为vis[x][y]==1只代表这个点不能走 不能直接return 应该再找其他的点dfs 然后再return