蓝桥杯算法提高VIP-棋盘多项式 （C语言代码）

解题思路:

注意事项:

参考代码:

#include<iostream>

using namespace std;

bool qp[9][9];//存储期盼 

bool chess[9][9];//存储棋子 

int num;//代表这一次总共要放的棋子个数 

int cnt;//记录此次的方案数 

int n;

void dfs(int ii,int jj,int now)//ii，jj代表当前的位置，now代表现在已经放置的棋子个数 

{

if(now>=num){//满足条件，方案数+1 

cnt++;

return;

}

if(jj>n){//来到棋盘边界处，向下一个位置移动 

ii++;

jj=1;

if(ii>n){

return;

}

dfs(ii,jj,now);

return;

}

if(qp[ii][jj]==0){//如果当前位置不能放棋子，则直接前往下一个位置 

dfs(ii,jj+1,now);

return;

}

bool flag=true;//判断当前位置是否能放棋子 

for(int i=ii-1;i>=1;i--)//向上判断 

{

if(chess[i][jj]){

flag=false;

break;

}

if(qp[i][jj]==0){

break;

}

}

for(int j=jj-1;j>=1;j--)//向左判断 

{

if(chess[ii][j]){

flag=false;

break;

}

if(qp[ii][j]==0){

break;

}

}

if(flag){

chess[ii][jj]=true;

dfs(ii,jj+1,now+1);

chess[ii][jj]=false;

dfs(ii,jj+1,now);

}else{

dfs(ii,jj+1,now);

}

}

int main()

{

cin>>n;

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

{

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

{

cin>>qp[i][j];

}

}

for(int i=1;i<=n*n;i++)

{

num=i;

cnt=0;

dfs(1,1,0);

if(cnt!=0){

cout<<cnt<<endl;

}else{

break;

}

}

return 0;

}