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

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 9;
int graph[N][N];
int vis[N][N];
int ans[N*N];
bool check(int x,int y,int n)
{
	int lx=x,rx=x;
	int uy=y,dy=y;
	while(lx-1>=0 && graph[lx-1][y]==1) lx--;
	while(rx+1<n && graph[rx+1][y]==1) rx++;
	while(uy-1>=0 && graph[x][uy-1]==1) uy--;
	while(dy+1<n && graph[x][dy+1]==1) dy++;	
	for(int i=lx;i<=rx;i++) if(vis[i][y]==1 && i!=x) return false;
	for(int i=uy;i<=dy;i++) if(vis[x][i]==1 && i!=y) return false;
	return true;
} 
void dfs(int x,int y,int n,int cur)
{
	if(cur<=n*n)
	{
		cout<<x<<" "<<y<<" "<<cur<<endl; 
		ans[cur]++;
	}
	//这里的循环便是可以让我们从不同的位置检索下一个可能的节点 
	for(int i=x;i<n;i++)
	{
		int c;
		if(i==x) c=y;
		else c=0;
		for(int j=c;j<n;j++)
		{
			if(vis[i][j]==1 || graph[i][j]==0) continue;
			if(check(i,j,n))//说明可以放置一个车子 
			{
				vis[i][j]=1;
				dfs(i,j,n,cur+1);//只有当车子数量加一之后才进入下一层递归 
				vis[i][j]=0;
			}	
		}	
	} 
}
int cnt=0;
int main(void)
{
	freopen("D:\\input1.txt","r",stdin);
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			scanf("%d",&graph[i][j]);
		}
	}
	memset(vis,0,sizeof(vis));
	dfs(0,0,n,0);//进入递归 
	for(int i=1;i<=n*n;i++)
	{
		if(ans[i]!=0) printf("%d\n",ans[i]);
		else break;	
	}
	return 0;	
}