1 条题解

  • 0
    @ 2025-10-10 20:13:35

    C++ :

    #include <bits/stdc++.h>
    using namespace std;
    
    int a[10][10];
    bool f[10][10];
    int t,n,m,ans;
    int fx[9] = {0,-1,-1,-1,0,1,1,1,0};
    int fy[9] = {0,-1,0,1,1,1,0,-1,-1};
    
    void dfs(int x,int y,int sum)
    {
        if(x > n) //最后一行搜索结束
        {
            ans = max(ans,sum);
            return ;
        }
    
        //检验当前点的8方向,如果没有点被选中过,则将该点选中
        int c = 0;
        for(int i = 1; i <= 8; i++)
        {
            if(f[x+fx[i]][y+fy[i]]==true) c++;
        }
    
        int tx = x,ty = y + 1;//讨论要去的下一个点
        if(ty > m)  //出边界,看下一行第1个
        {
            tx = x + 1;
            ty = 1;
        }
    
        //如果周边8点没选过
        if(c == 0)
        {
            f[x][y] = true;
            dfs(tx,ty,sum+a[x][y]);//选择该数
            f[x][y] = false;
        }
    
        dfs(tx,ty,sum);//放弃对该数的选择
    }
    
    int main()
    {
    
        cin>>n>>m;
        memset(f,0,sizeof(f));
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                cin>>a[i][j];
            }
        }
        ans = 0;
        dfs(1,1,0);
        cout<<ans<<endl;
    
        return 0;
    }
    
    

    信息

    ID
    1099
    时间
    1000ms
    内存
    512MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者