易码技术论坛

 找回密码
 加入易码
搜索
查看: 232747|回复: 9

[源码] ACM题一

[复制链接]
发表于 2006-5-9 21:55:00 | 显示全部楼层
n的范围和k的范围?
 楼主| 发表于 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 | 显示全部楼层


  1. #include <stdio.h>
  2. #include <string.h>
  3. int cnt;
  4. int n,k;
  5. char d[100];
  6. int canput(int pos)
  7. {
  8. int x,y,i;
  9. x=pos%n;
  10. y=pos/n;
  11. for (i=0;i<x;i++) if (d[y*n+i]==1) return 0;
  12. for (i=0;i<y;i++) if (d[i*n+x]==1) return 0;
  13. return 1;
  14. }
  15. void exe(int pos,int count)
  16. {
  17. if (count==k) {cnt++;return;}
  18. if (pos==n*n) return;
  19. if (canput(pos))
  20. {
  21.   d[pos]=1;
  22.   exe(pos+1,count+1);
  23.   d[pos]=0;
  24.   exe(pos+1,count);
  25. }
  26. else exe(pos+1,count);
  27. return;
  28. }
  29. int main()
  30. {
  31. while(scanf("%d%d",&n,&k)!=EOF)
  32. {
  33.   cnt=0;
  34.   memset(d,0,100);
  35.   exe(0,0);
  36.   printf("%d\n",cnt);
  37. }
  38. }


复制代码


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

不知道正不正确。
 楼主| 发表于 2006-5-9 22:37:00 | 显示全部楼层
呵呵,正确,但不是最佳算法.
发表于 2006-5-10 17:27:00 | 显示全部楼层
动态规划可能快一点。
 楼主| 发表于 2006-5-9 21:09:11 | 显示全部楼层 |阅读模式
我也来一题:

在n*n的方格中放入k个棋子,要求任意两个棋子不能相邻,即不能这样放:
●●或●□但可以这样放:●□或□●
□□   ●□               □●  ●□
求出共有几种放法?
例如:输入:n=4,k=4
      输出:24
发表于 2010-7-26 03:12:38 | 显示全部楼层

hehe

是8皇后问题么?
发表于 2010-7-26 10:22:34 | 显示全部楼层
我的想法是
n*n的矩阵,有子为1无子为0
下一个棋子的位置循环起始为上一个棋子位置+2
判定标准为每一个棋子-n没有被占用
就是不知道执行起来效率怎么样
发表于 2010-7-26 10:39:33 | 显示全部楼层
感觉用a[k]来表示棋子的位置好点,判定方法一样,中午吃饭的时候写个试试,嘿嘿
对了,FF里面发帖的时候看不到右边的默认表情~囧

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

[ 本帖最后由 Still4 于 2010-7-26 11:32 编辑 ]
您需要登录后才可以回帖 登录 | 加入易码

本版积分规则

Archiver|手机版|小黑屋|EMAX Studio

GMT+8, 2024-3-29 00:11 , Processed in 0.011082 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表