频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
算法提高 棋盘多项式
2017-03-20 09:29:33      个评论    来源:qq_25308331的博客  
收藏   我要投稿
算法提高 棋盘多项式:八皇后问题是在棋盘上放皇后,互相不攻击,求方案。变换一下棋子,还可以有八车问题,八马问题,八兵问题,八王问题,注意别念反。在这道题里,棋子换成车,同时棋盘也得换,确切说,是进行一些改造。

比如现在有一张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   

int N=3;
int board[11][11]={
	{0},
	{0 , 1, 0, 1},
	{0 , 1, 1, 1},
	{0 , 1, 0, 1},
};
int count[65]={0};

int candown(int x,int y){
	 int i=0;
     if(board[x][y]==0) return 0;
	 for(i=1;i+x<=N;i++){
         if(board[x+i][y]==0) break;
		 if(board[x+i][y]==2) return 0;
	 }
	 for(i=1;i+y<=N;i++){
         if(board[x][y+i]==0) break;
		 if(board[x][y+i]==2) return 0;
	 }
	 for(i=1;x-i>=1;i++){
         if(board[x-i][y]==0) break;
		 if(board[x-i][y]==2) return 0;
	 }
	 for(i=1;y-i>=1;i++){
         if(board[x][y-i]==0) break;
		 if(board[x][y-i]==2) return 0;
	 }
	 return 1;
}

void init(){
    int i,j;
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
			if(board[i][j]==2) board[i][j]=1;
}

void fun(int n,int num,int startX,int startY){
	int i,j;
    if(n<1) count[num]++;
	else{
		for(i=startX;i<=N;i++){
            if(i==startX) j=startY; else j=1;
			for(j;j<=N;j++) {
                if(candown(i,j)){
                    board[i][j]=2;
					fun(n-1,num,i,j+1);
					board[i][j]=1;
				}
			}
		}
	}
}

int main()  
{  
    int i,j;
	scanf("%d",&N);
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++) scanf("%d",&board[i][j]);   /* */
	for(i=1;;i++){
           fun(i,i,1,1);
		   init();
		   if(count[i]==0) break;
		   printf("%d\n",count[i]);
	}    /*  */
	return 0;
}  
点击复制链接 与好友分享!回本站首页
上一篇:Java实现图片验证码
下一篇:多线程复制
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训

版权所有: 红黑联盟--致力于做实用的IT技术学习网站