我不是张玉想

用户名：ZYX666

访问量：5832

签　名：

---------------------------靓仔靓铝分割线---------------------------

等　　级
排　　名	699
经　　验	3926
参赛次数	8
文章发表	13
年　　龄	0
在职情况	学生
学　　校	东华理工大学
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

我不是张玉想——新生舞会-题解（C++map容器解题代码）
浏览：395

我不是张玉想——等差数列-题解（三个平台数据都可AC，原来的是错解，现已更新）
浏览：532

我不是张玉想——奇怪的数列-题解（C++代码）
浏览：277

你可能喜欢

我不是张玉想——棋盘多项式-题解（C++代码）

　　作者: 我不是张玉想　　　　发表时间：2020-02-18 18:42:00 浏览：353　|　评论：0　

原题链接：蓝桥杯算法提高VIP-棋盘多项式

## 一、解题思路：<<深搜DFS>>

#### 1、和大多数题类似，运用深搜DFS即可（具体详见下方完整代码）
#### 2、编写check函数、DFS函数及主函数，完成代码编写。
#### 3、运行检验代码正确与否即可
# 二、完整代码
```cpp
#include<iostream>
using namespace std;
int n;//棋盘阶数
int a[1000000]={0};//用于存放放K个棋子的方案数，从下表1开始存
int map[8][8]={0};//棋盘数组
int sum=0;//用于存放深搜过程中棋盘已放棋子数目
int ways=0;//用于存放方案数
int sum1=0;//K=1的方案数，即棋盘上1的个数
int check(int row,int culum)//检查该处能否存放棋子
{
	if(map[row][culum]==0)//此处是否为洞
	{
		return 0;
	}
	//左 
	for(int i=row,j=culum-1;j>=0&&map[i][j]!=0;j--)
	{
		if(map[i][j]==-1)
		{
			return 0;
		}
	}
	//右
	for(int i=row,j=culum+1;j<=8&&map[i][j]!=0;j++)
	{
		if(map[i][j]==-1)
		{
			return 0;
		}
	}
	//上
	for(int i=row-1,j=culum;i>=0&&map[i][j]!=0;i--)
	{
		if(map[i][j]==-1)
		{
			return 0;
		}
	}
	//下 
	for(int i=row+1,j=culum;i<=8&&map[i][j]!=0;i++)
	{
		if(map[i][j]==-1)
		{
			return 0;
		}
	}
	return 1;
}
void dfs(int row,int culum)//深搜函数
{
	if(row==n)
	{
		return;
	 } 
	else
	{
		if(check(row,culum)==1)//在此处放一个棋子
		{
			sum++;
			if(sum>1)
			{//若此时已放棋子数大于1，表面放K个棋子的方案又多一种
				a[sum]++;//个人觉得此处挺巧的（个人拙见，勿喷，哈哈）
			}
			map[row][culum]=-1;
			dfs(row+(culum+1)/n,(culum+1)%n);
			map[row][culum]=1;
			sum--;			
		}
		//不在此处放棋子或不能放棋子，直接往下搜
		dfs(row+(culum+1)/n,(culum+1)%n);//此处表示方法从别人那里学来                                        //的，推荐给你们（会的就算了）
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)//初始化棋盘
	{
		for(int j=0;j<n;j++)
		{
			cin>>map[i][j];
			if(map[i][j]==1)
			{
				sum1++;//计算1的个数
			}
		}
	 } 
	 a[1]=sum1;
	dfs(0,0);
	for(int i=1;a[i]!=0;i++)
	{
		cout<<a[i]<<endl;
	}
	return 0;
}
```
# 三、代码通过情况
![](/image_editor_upload/20200218062601_30097.png)

------------

##### PS：以上为本人拙见，写的匆忙，变量名取得些许潦草哈哈，若有错误，望大家不吝赐教，共同进步，十分感谢！！！

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

我不是张玉想

TA的其他文章

你可能喜欢

弟弟的作业（C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

人民币问题（C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

我不是张玉想——棋盘多项式-题解（C++代码）

评论区

精彩推荐

最小公倍数（C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【矩阵】（C++代码）

完数（C语言代码）

字符逆序（C语言代码）

我不是张玉想

TA的其他文章

你可能喜欢

弟弟的作业 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

人民币问题 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

我不是张玉想——棋盘多项式-题解（C++代码）

评论区

精彩推荐

最小公倍数 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【矩阵】 （C++代码）

完数 （C语言代码）

字符逆序 （C语言代码）

弟弟的作业（C语言代码）

人民币问题（C语言代码）

　　评论区

最小公倍数（C语言代码）

【矩阵】（C++代码）

完数（C语言代码）

字符逆序（C语言代码）