蓝桥杯 算法提高 棋盘多项式

算法提高 棋盘多项式  

时间限制：1.0s   内存限制：256.0MB

    

　　
　　棋盘多项式

问题描述

　　八皇后问题是在棋盘上放皇后，互相不攻击，求方案。变换一下棋子，还可以有八车问题，八马问题，八兵问题，八王问题，注意别念反。在这道题里，棋子换成车，同时棋盘也得换，确切说，是进行一些改造。比如现在有一张n*n的棋盘，我们在一些格子上抠几个洞，这些洞自然不能放棋子了，会漏下去的。另外，一个车本来能攻击和它的同行同列。现在，你想想，在攻击的过程中如果踩到一个洞，便会自取灭亡。故，车的攻击范围止于洞。
　　此题，给你棋盘的规模n，以及挖洞情况，求放k个车的方案数(k从0到最多可放车数)

输入格式

　　第一行一个整数n表示棋盘大小
　　接下来n行，每行n个用空格隔开的数字0或1，0的形状表示洞，1表示没有洞

输出格式

　　若干行，第i行表示放i个车的方案数

样例输入

3
1 0 1
1 1 1
1 0 1

样例输出

7
12
4

数据规模和约定

　　n<=8

/*
思路：枚举每个格子，放或者不放 到终点几个就累加 
*/
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cstdio>
#include <math.h>
using namespace std;
const int N=10;
int map[N][N];    //0洞 1可以放 2放了 
int re[N*N];
int len;  //结果数的长度 
int n;
inline bool check(int x,int y){
	int i;
	for(i=y-1;i>=0;i--) {   //左横 
	      if(map[x][i]==2)      //遇到车 
	       return false;
	    if(map[x][i]==0)       //遇到洞 不会攻击到别人 
	      break;
	}

	for(i=y+1;i<n;i++) {   //右横 
	       if(map[x][i]==2)      //遇到车 
	       return false;
	    if(map[x][i]==0)       //遇到洞 不会攻击到别人 
	      break;
	}


	for(i=x-1;i>=0;i--)  {        //左竖 	
	   if(map[i][y]==2)
	   return false;

	   if(map[i][y]==0)
	   break;
	}    

	   for(i=x+1;i<n;i++)  {        //右竖 	
	   if(map[i][y]==2)
	   return false;

	   if(map[i][y]==0)
	      break;
	}    

	   return true;
}
void dfs(int now,int sum){
	if(now>=n*n){
		re[sum]++; 
		return;
	}
	int x=now/n;
	int y=now%n;

	if(map[x][y]==1){
		if(check(x,y)){
			map[x][y]=2;
			dfs(now+1,sum+1);
			map[x][y]=1;
		}	
	}	
	dfs(now+1,sum);
}
int main(){    
    int i,j;
    while(cin>>n){
    	for(i=0;i<n;i++)
    	  for(j=0;j<n;j++){
    	  	cin>>map[i][j];
		  }

		  memset(re,0,sizeof(re)); 

			dfs(0,0); 


		for(i=1;i<n*n;i++){
			if(re[i]!=0){
				cout<<re[i]<<endl;
			} 
		    else 
			    break; 
		}
	}
	return 0;
}