非晚

用户名：zhaoyinger

访问量：3955

签　名：

冲冲冲！

等　　级
排　　名	5368
经　　验	1551
参赛次数	0
文章发表	12
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-色盲的民主-题解(C++代码)-----小白
浏览：211

蓝桥杯算法提高VIP-超级玛丽-题解(C++代码)-----DFS（40行）不太懂动态规划
浏览：278

蓝桥杯算法提高VIP-连接乘积-题解(C++代码)
浏览：261

你可能喜欢

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

　　作者: 非晚　　　　发表时间：2020-03-12 10:52:40 浏览：593　|　评论：0　

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

小菜鸟做了这个题做了五个小时，代码其实写的不是很专业，但是还是想写一个题解记录一下自己的进步，嘿嘿。
我也加了很多注释，希望能够帮到你。
```cpp
#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
//n*n的棋盘 
int n;
//表示棋盘 
int map[8][8];
//表示该点是否访问过 
int vis[8][8];
//用于记录每一个位置开始寻找放i个车的方案数
int ans=0;
//函数 
bool check(int k,int s){
	//判断寻找到的点在同行或同列的方向上是否已经有放置了的点，与放置了的点中间是否有0间隔 
	int no_x=0;
	int no_y=0;
	//节省时间，行和列同时进行寻找，不然会超时 
	for(int a=0;a<n;a++){
		//如果行上有点被访问 
		if(vis[a][s]==1){
			//位置在该点前 
			if(a<k){
				int p=a;
				for(p;p<k;p++){
					//如果中间有0间隔，name该点就可以放置 
					if(map[p][s]==0){
						break;
					}
				}
				//如果没有0间隔，就不能放 
				if(p==k){
					no_y=1;
				}
			}
			//位置在该点后 
			if(a>k){
				int p=k;
				//与上相同 
				for(p;p<a;p++){
					if(map[p][s]==0){
						break;
					}
				}
				if(p==a){
					no_y=1;
				}
			}
										
		}
		//按列寻找与按行的方法相同 
		if(vis[k][a]==1){
			if(a<s){
				int p=a;
				for(p;p<s;p++){
					if(map[k][p]==0){
						break;
					}
				}
				if(p==s){
					no_x=1;
				}
			}
			if(a>s){
				int p=s;
				for(p;p<k;p++){
					if(map[k][p]==0){
						break;
					}
				}
				if(p==k){
					no_x=1;
				}
			}
										
		}
	}
	if(no_y==0&&no_x==0){
		return true;				
	}
	return false;
}
int getAns(int start,int end,int m){
	//如果一条长为m的路径被寻找到 ，方案数+1 
	//map[start][end]!=0的原因是寻找路径长为1是，map为0的点肯定是不能放置的 
	if(map[start][end]!=0&&m==1){
		ans++;
	}
	else{
		int i=start;
		int j=end;
		//该点可以放置一个棋子 前提是没有被访问过，且map[i][j]!=0;
		if(map[i][j]==1&&vis[i][j]==0){
			//该点可放置棋子，该点被访问 
			vis[i][j]=1;
			//寻找与该点在同一行的可以放置的棋子 
			int k=i;
			//从j+1开始找的目的是为了不重复得到一个结果 
			for(int s=j+1;s<n;s++){
				//寻找到的点满足可放置的大前提 
				if(vis[k][s]==0&&map[k][s]==1){
					//行列都满足可以放置，才可以放置 
					if(check(k,s)){
						getAns(k,s,m-1);
						vis[k][s]=0;
					}
				}
			}
			//寻找与放置的点不是同一行的可以放置的点，从下一行开始 
			//之所以按同行和不同行分开是为了避免重复 
			for(int k=i+1;k<n;k++){
				for(int s=0;s<n;s++){
					if(vis[k][s]==0&&map[k][s]==1){
						//与上面方法相同 
						if(check(k,s)){
							getAns(k,s,m-1);
							vis[k][s]=0;	
						}
								
					}
				}
			}
		}
	}
	//回溯 
	vis[start][end]=0;
	return ans;
}

int main(){
	//把所有点置为为访问 
	memset(vis,0,sizeof(vis));
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>map[i][j];
		}
	}
	//从放1个棋子开始执行 
	for(int line=1;;line++){
		int sum=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				ans=0;
				//执行完所有位置都要清零 
				memset(vis,0,sizeof(vis));
				//每个点得到的结果相加 
				sum+=getAns(i,j,line);
			}
		}
		if(sum!=0)
			cout<<sum<<endl;
		else
			break;
	}
	return 0;
}
```

0.0分

11 人评分

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

非晚

TA的其他文章

你可能喜欢

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

汽水瓶（C语言代码）

printf基础练习2 （C语言代码）

聪明的美食家（C语言代码）

C二级辅导-求偶数和（C语言代码）

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

评论区

精彩推荐

点我有惊喜！你懂得！

剔除相关数（C语言代码）

上车人数（C语言代码）

printf基础练习2 （有点不明白）

WU-判定字符位置（C++代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

简单的a+b （C语言代码）

【计算直线的交点数】（C语言代码）

水仙花（C语言代码）

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

非晚

TA的其他文章

你可能喜欢

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

汽水瓶 （C语言代码）

printf基础练习2 （C语言代码）

聪明的美食家 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

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

评论区

精彩推荐

点我有惊喜！你懂得！

剔除相关数 （C语言代码）

上车人数 （C语言代码）

printf基础练习2 （有点不明白）

WU-判定字符位置 （C++代码）

WU-C语言程序设计教程（第三版）课后习题11.11 （C++代码）（想学链表的可以看看）

简单的a+b （C语言代码）

【计算直线的交点数】 （C语言代码）

水仙花 （C语言代码）

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

汽水瓶（C语言代码）

聪明的美食家（C语言代码）

C二级辅导-求偶数和（C语言代码）

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

　　评论区

剔除相关数（C语言代码）

上车人数（C语言代码）

WU-判定字符位置（C++代码）

【计算直线的交点数】（C语言代码）

水仙花（C语言代码）