蓝桥杯c++A组第二个填空题

Question

c++ A组蓝桥杯填空题第二题下棋问题

#include <iostream>

using namespace std;
const int N=26;
int g[N];
long long ans;

bool check_s()
{
    int s[N];
    for(int i=1;i<=25;i++) s[i]=s[i-1]+g[i];
    if(s[5]-s[0]==5||s[10]-s[5]==5||s[15]-s[10]==5||s[20]-s[15]==5||s[25]-s[20]==5) return false;
    if(s[5]-s[0]==0||s[10]-s[5]==0||s[15]-s[10]==0||s[20]-s[15]==0||s[25]-s[20]==0) return false;
    int col[5]={0};
    for(int i=1;i<=5;i++)
    {
        col[i]=0;
        for(int j=i;j<=25;j+=5)
        {
            col[i]=col[i]+g[j];
        }
    }
    if(col[1]==0||col[2]==0||col[3]==0||col[4]==0||col[5]==0) return false;
    if(col[1]==5||col[2]==5||col[3]==5||col[4]==5||col[5]==5) return false;
    if(g[1]==1&&g[7]==1&&g[13]==1&&g[19]==1&&g[25]==1) return false;
    if(g[1]==0&&g[7]==0&&g[13]==0&&g[19]==0&&g[25]==0) return false;
    if(g[5]==1&&g[9]==1&&g[13]==1&&g[17]==1&&g[21]==1) return false;
    if(g[5]==0&&g[9]==0&&g[13]==0&&g[17]==0&&g[21]==0) return false;

    return true;
    
}
void dfs(int u,int num)
{
    
    if(num==13&&check_s()) 
    {
        ans++;
        return;
    }
    if(u>25) return;
    //不下
    g[u+1]=0;
    dfs(u+1,num);
    //下
    g[u+1]=1;
    dfs(u+1,num+1);

}

int main()
{
    dfs(0,0);
    cout<<ans<<endl;
    return 0;
}

为什么最后输出是1，ans明明加了很多次，甚至不++，输出也是1，这是为什么呀？为什么我这段代码搜不出来呀？求佬解答。

Answer 1

引自免费微信小程序：皆我百晓生

在给定的代码中，ans 变量用于计算满足条件的棋局数量，但是在 dfs 函数中，递归调用时没有正确地更新 ans 的值。实际上，在每次调用 dfs(u+1, num) 之后，无论是否执行了 ans++;，都返回了之前计算的 ans 值，这导致最终结果只增加了一次。

为了解决这个问题，你需要在递归过程中正确地累加答案。当满足条件（即 num == 13 && check_s()）时，应该将当前的 ans 值传递给父函数，并且递增它。下面是修复后的代码：

#include <iostream>
using namespace std;
const int N = 26;
int g[N];
long long ans;

bool check_s()
{
    // ... (原来的代码保持不变)
}

void dfs(int u, int num, long long& ansCurrent)
{
    if (num == 13 && check_s())
    {
        ansCurrent += 1; // 将找到的解加入到当前的答案中
        return;
    }
    if (u > 25) return;
    // 不下
    g[u + 1] = 0;
    dfs(u + 1, num, ansCurrent); // 传递当前的 ansCurrent 给子函数
    // 下
    g[u + 1] = 1;
    dfs(u + 1, num + 1, ansCurrent); // 在这里递增 num 后再传递给子函数

    // 因为我们在递归调用后立即恢复原状，所以不需要在这里做任何操作
    // g[u + 1] = 0; // 这一行可以删除
}

int main()
{
    dfs(0, 0, ans); // 初始化 ans 并将其作为引用传递给 dfs 函数
    cout << ans << endl;
    return 0;
}

在这个版本的代码中，我添加了一个额外的参数 ansCurrent 到 dfs 函数中，这个参数是一个 long long 类型的引用，用来保存当前层的满足条件的棋局数。当在某个深度找到一个符合条件的棋局时，就将 ansCurrent 自增并返回给上一层。这样，每一层递归都会累积它们找到的解，最终得到正确的答案。

运行修改后的代码，你应该会得到正确的答案。