「Luogu1377」m国王
题目描述
天天都是n皇后，多么无聊啊。我们来一道m国王游戏吧！
题目是这样的，在n*n的格子里放m个国王，使他们不互相攻击，有多少种放法呢？（可以为0）。注意国王可攻击的格子是它周围的上、下、左、右、左上、左下、右上、右下等8个格子。
输入
输入只有一行，有两个整数n与m。100%的数据满足n<=8,m<=n*n
输出
输出只有一个整数，为所求的方案数。
样例输入
2 2
样例输出
0
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<cstdio> #include<iostream> #include<cstring> #define searchnext(x,y,k) y==n?search(x+1,1,k):search(x,y+1,k) using namespace std; int n,m; int ans; int mp[10][10]; bool putit(int x,int y) { for(int i=x-1;i<=x+1;i++) for(int j=y-1;j<=y+1;j++) if(mp[i][j])return 0; mp[x][y]=1; return 1; } void search(int x,int y,int k) { if(k==m){ans++;return;} if(x>n)return; for(int i=y;i<=n;i++) if(putit(x,i)) { searchnext(x,i,k+1); mp[x][i]=0; } for(int i=x+1;i<=n;i++) for(int j=1;j<=n;j++) { if(putit(i,j)) { searchnext(i,j,k+1); mp[i][j]=0; } } } int main() { scanf("%d%d",&n,&m); search(1,1,0); printf("%d",ans); return 0; } |
Subscribe
计数器 9298401
OI 课件=>
OI 课件=>