题解 P1479 【宿舍里的故事之五子棋】

· · 题解

我也不知道这叫什么解法，只知道棋子可以放或不放。

因为棋盘较小，可以直接查找多少五子。

于是代码如下

#include <iostream>
#include <cstring>
using namespace std;
bool f[15];//可连成数
int n;
bool a[6][6]={false};//所有位置都不放
int ans=0;
void c(){
    int q=0;
    for(int i=1;i<=5;i++){
        if(a[i][1]&&a[i][2]&&a[i][3]&&a[i][4]&&a[i][5])q++;
        if(a[1][i]&&a[2][i]&&a[3][i]&&a[4][i]&&a[5][i]q++; 
    }//横竖五子
    if(a[1][1]&&a[2][2]&&a[3][3]&&a[4][4]&&a[5][5])q++;
    if(a[1][5]&&a[2][4]&&a[3][3]&&a[4][2]&&a[5][1])q++;
    //两条斜边五子
    f[q]=true;可连成数标上对；
}
void dfs(int i,int j,int sum){
    if(i==6||sum==n+1){//如果棋子放完或无法继续就停止
     if(sum==n+1)
        c();//如果棋子放满就开始计可连成数。
                return;
     }
     if(j==6)dfs(i+1,1,sum);
     else{
     a[i][j]=true;//放
     dfs(i,j+1,sum+1);
     a[i][j]=false;//不放
     dfs(i,j+1,sum);
     a[i][j]=false;//回溯
     }
}
int main(){
    cin>>n;
    dfs(1,1,1);
    for(int i=1;i<=15;i++){
        if(f[i])ans+=i;//加上可连成数
    }
    cout<<ans<<endl;输出
    return 0;//拜拜
}

用心写题解，希望给大家带来点帮助呀！