算法提高棋盘多项式（深搜）

蔚落 2022-09-30 10:55 126阅读 0赞

问题描述

八皇后问题是在棋盘上放皇后，互相不攻击，求方案。变换一下棋子，还可以有八车问题，八马问题，八兵问题，八王问题，注意别念反。在这道题里，棋子换成车，同时棋盘也得换，确切说，是进行一些改造。比如现在有一张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

思路：

在地图上遇到0就跳过，判断放置位置的合法性

代码：

#include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    int n,map[9][9],cnt=0;
    int check(int xx,int yy)//第x行,第y个位置 
    {
    	int i,j,t1=0,t2=0;
    	if (map[xx][yy] == 2 || map[xx][yy] == 0) //是洞
    	  return 1;
    	for (i=xx-1; i>=1; i--) //找出0的位置
    	{
    		if (map[i][yy] == 0)
    		{
    			t1 = i;
    			break;
    		 } 
    	}
    	for (i=xx-1; i>=1; i--)
    	{
    		if (map[i][yy] == 2)//找出2的位置，2代表是棋子
    		{
    			t2 = i;
    			break;
    		}
    	}
    	if (t2 > t1) //2比0较近，说明不能放
    	{
    		return 1;
    	}
    	t1 = t2 = 0;
    	for (i=yy-1; i>=1; i--)//同上，找2，和0 的位置
    	{
    		if (map[xx][i] == 0)
    		{
    			t1 = i;
    			break;
    		}
    	}
    	for (i=yy-1; i>=1; i--)
    	{
    		if (map[xx][i] == 2)
    		{
    			t2 = i;
    			break;
    		}
    	}
    	if (t2 > t1)
    	 return 1; 
    	return 0; //可以放
    }
    void dfs(int ss,int x,int sum,int pos)//放ss个棋子，x行下标，sum个棋子，pos记录下一个循环位置
    {
    	int i,j,t;
    	if (x > n)
    	 return ;
    	if (sum >= ss)//一种方案
    	{
    		cnt++;
    		return ;
    	}
    	for (i=pos; i<=n; i++)
    	{
    		if (check(x,i)) //发送行列，判断是否可以放棋子
    		continue;
    		t = map[x][i];
    		map[x][i] = 2;
    		dfs(ss,x,sum+1,i+1);//增加列
    		map[x][i] = t;//回溯，恢复原样
    	}
    	dfs(ss,++x,sum,1);//换行
    }
    int main()
    {
    	int i,j; 
    	cin>>n;
    	for (i=1; i<=n; i++)
    	for (j=1; j<=n; j++)
    	{
    		cin>>map[i][j];
    	}
    	for (i=1; ;i++)
    	{
    		cnt=0;
    		dfs(i,1,0,1);
    		if (cnt==0)
    		{
    			break;
    		}
    		cout<<cnt<<endl;
    	}
    	return 0;
     }