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

数据规模和约定
n< =8

输入
第一行一个整数n表示棋盘大小
接下来n行，每行n个用空格隔开的数字0或1，0的形状表示洞，1表示没有洞
输出
若干行，第i行表示放i个车的方案数
样例输入
3
1 0 1
1 1 1
1 0 1
样例输出
7
12
4
提示
C语言在线学习平台微信号dotcpp
来源
算法提高

#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;   
}