8.23测试总结

Luck_Deepsea · 2025-08-23 17:29:23 · 算法·理论

8.21测试总结

T658911 五子棋

得分:20

应得:100

考点:深搜-深度优先搜索（dfs）

错误思路:暴力-打表，写出n>=...就将计数器加...

正确思路:搜索枚举出所有情况，如果没出现就将计数器加k，输出。(k是check函数中的表示有多少个5个子起来的直线)

check函数：

int check(){
    int k=0;
    for(int i=1;i<=5;i++){
        int cnt=0;
        for(int j=1;j<=5;j++)cnt+=vis[i][j];
        if(cnt==5)k++;
    }
    for(int i=1;i<=5;i++){
        int cnt=0;
        for(int j=1;j<=5;j++)cnt+=vis[j][i];
        if(cnt==5)
            k++;
    }
    int cnt=0;
    for(int i=1;i<=5;i++)cnt+=vis[i][i];
    if(cnt==5)k++;
    cnt=0;
    for(int i=1;i<=5;i++)cnt+=vis[i][6-i];
    if(cnt==5)k++;
    return k;
}

搜索过程：

void dfs(int x,int y,int cnt){
    if(cnt==n){
        int k=check();
        tong[k]++;
        if(tong[k]==1)ans+=k;
        return ;
    }
    if(x==6)return ;
    if(y==5){
        vis[x][y]=1;
        dfs(x+1,1,cnt+1);
        vis[x][y]=0;
        dfs(x+1,1,cnt);
    }
    else{
        vis[x][y]=1;
        dfs(x,y+1,cnt+1);
        vis[x][y]=0;
        dfs(x,y+1,cnt);
    }
    return ;
}

完整代码:

#include<bits/stdc++.h>
using namespace std;
int n;
int tong[25];
int ans=0;
int vis[25][25];
int check(){
    int k=0;
    for(int i=1;i<=5;i++){
        int cnt=0;
        for(int j=1;j<=5;j++)cnt+=vis[i][j];
        if(cnt==5)k++;
    }
    for(int i=1;i<=5;i++){
        int cnt=0;
        for(int j=1;j<=5;j++)cnt+=vis[j][i];
        if(cnt==5)
            k++;
    }
    int cnt=0;
    for(int i=1;i<=5;i++)cnt+=vis[i][i];
    if(cnt==5)k++;
    cnt=0;
    for(int i=1;i<=5;i++)cnt+=vis[i][6-i];
    if(cnt==5)k++;
    return k;
}
void dfs(int x,int y,int cnt){
    if(cnt==n){
        int k=check();
        tong[k]++;
        if(tong[k]==1)ans+=k;
        return ;
    }
    if(x==6)return ;
    if(y==5){
        vis[x][y]=1;
        dfs(x+1,1,cnt+1);
        vis[x][y]=0;
        dfs(x+1,1,cnt);
    }
    else{
        vis[x][y]=1;
        dfs(x,y+1,cnt+1);
        vis[x][y]=0;
        dfs(x,y+1,cnt);
    }
    return ;
}
int main()
{
    cin>>n;
    dfs(1,1,0);
    cout<<ans<<endl;
    return 0;   
}