无言的梦 发表于 2006-5-9 21:55:00

n的范围和k的范围？

yan 发表于 2006-5-9 22:01:00

补上:1<=n<=10 0<=k<=n*n

无言的梦 发表于 2006-5-9 22:09:00

范围蛮小的……俺用穷举来做。。。

无言的梦 发表于 2006-5-9 22:25:00



#include <stdio.h>
#include <string.h>
int cnt;
int n,k;
char d;
int canput(int pos)
{
int x,y,i;
x=pos%n;
y=pos/n;
for (i=0;i<x;i++) if (d==1) return 0;
for (i=0;i<y;i++) if (d==1) return 0;
return 1;
}
void exe(int pos,int count)
{
if (count==k) {cnt++;return;}
if (pos==n*n) return;
if (canput(pos))
{
d=1;
exe(pos+1,count+1);
d=0;
exe(pos+1,count);
}
else exe(pos+1,count);
return;
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
cnt=0;
memset(d,0,100);
exe(0,0);
printf("%d\n",cnt);
}
}




简单得测试了几个数据。。。

不知道正不正确。

yan 发表于 2006-5-9 22:37:00

呵呵,正确,但不是最佳算法.

cheelumbill 发表于 2006-5-10 17:27:00

动态规划可能快一点。

yan 发表于 2006-5-9 21:09:11

ACM题一

我也来一题:

在n*n的方格中放入k个棋子,要求任意两个棋子不能相邻,即不能这样放:
●●或●□但可以这样放:●□或□●
□□   ●□               □●●□
求出共有几种放法?
例如:输入:n=4,k=4
      输出:24

jltying 发表于 2010-7-26 03:12:38

hehe

是8皇后问题么？

Still4 发表于 2010-7-26 10:22:34

我的想法是
n*n的矩阵，有子为1无子为0
下一个棋子的位置循环起始为上一个棋子位置+2
判定标准为每一个棋子-n没有被占用
就是不知道执行起来效率怎么样

Still4 发表于 2010-7-26 10:39:33

感觉用a来表示棋子的位置好点，判定方法一样，中午吃饭的时候写个试试，嘿嘿
对了，FF里面发帖的时候看不到右边的默认表情~囧

唉，没注意到是坟……大家保重

[ 本帖最后由 Still4 于 2010-7-26 11:32 编辑 ]
页: [1]
查看完整版本: ACM题一