浙江中医药大学程序设计代表队2018年训练赛十三

Problem B: 棋盘多项式

Ti++me Li++mit:1 Sec
Memory Limit:128 MB

Submit:9

Solved:6

[​Submit​​][​Status​​][​Web Board​​]

Description

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

Input

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

n<=8

Output

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

Sample Input

3

1 0 1

1 1 1

1 0 1

Sample Output

7

12

4

【分析】

八皇后的.....略微修改版...并没有什么实质性的难度加深....注意细节吧

【代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int MAXN = 200;
const int INF = 1e9 + 7;

int n,a[MAXN][MAXN],f[MAXN],c[MAXN][MAXN];

bool judge(int x,int y) {
if(a[x][y] == 0) return false;
int i = x-1,j = y-1;
while(i>=0 && a[i][y] == 1) {
if(c[i][y] == 1) return false;
i--;
}
while(j>=0 && a[x][j] == 1) {
if(c[x][j] == 1) return false;
j--;
}
i = x+1;
while(i<n && a[i][y] == 1) {
if(c[i][y] == 1) return false;
i++;
}
j = y+1;
while(j<n && a[x][j] == 1) {
if(c[x][j] == 1) return false;
j++;
}
return true;
}

void dfs(int x,int y,int d) {
f[d]++;
for(int i=y+1; i<n; i++) {
if(judge(x,i)) {
c[x][i] = 1;
dfs(x,i,d+1);
c[x][i] = 0;
}
}
for(int i=x+1; i<n; i++) {
for(int j=0; j<n; j++) {
if(judge(i,j)) {
c[i][j] = 1;
dfs(i,j,d+1);
c[i][j] = 0;
}
}
}
}

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
while(cin >> n) {
memset(f,0,sizeof(f));
memset(c,0,sizeof(c));
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
cin >> a[i][j];
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(a[i][j] == 0) continue;
c[i][j] = 1;
dfs(i,j,1);
c[i][j] = 0;
}
}
for(int i=1; ; i++){
if(f[i] == 0) break;
cout << f[i] << endl;
}
}
return 0;
}