存档

文章标签 ‘POJ解题报告’

POJ 1321 棋盘问题[DFS]

2011年9月2日 没有评论

题目描述:在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
深搜,某一行放不放子的问题,大概是这样。中间判断一下某一列可不可以放子就好了。DFS返回条件是没有子可放了或者行数超出限制了。题目的数据量也不算大,直接用朴素的DFS就可以解决了。

#include <iostream>
#include <cstdio>
#i[......]

继续阅读

POJ 3278 Catch That Cow[BFS]

2011年9月2日 没有评论

复习数据结构ing,现在做做简单的题目。这是很久以前做的入门的题,翻出来了。用BFS做,如果只用一个队列,那么需要定义结构体来存储节点的位置信息和时间信息;如果不想用结构体的话需要两个队列,这样是一层一层的遍历节点,就只需要一个整型来记录时间信息了。其实都差不多,具体实现手法不同而已,BFS的思想是不变的。
下面两个版本的代码都贴一下,
POJ 3278 Catch That Cow[BFS] [http://poj.org/problem?id=3278]

#include <iost[......]

继续阅读

POJ 2420 A Star not a Tree? 多边形费马点

2010年11月29日 没有评论

POJ 2420 A Star not a Tree?实际上就是求平面内多边形的费马点问题,只不过这里要的不是点,而是最短距离。这里使用模拟退火的方法来逼近费马点。所谓费马点就是指满足这样条件的一个点:这个点到多边形所有定点的距离和最短。
平面上三角形的费马点有如下性质:

  1. 若三角形ABC的3个内角均小于120°,那么3条距离连线正好平分费马点所在的周角。
  2. 若三角形有一内角不小于120度,则此钝角的顶点就是距离和最小的点。

这次福州赛区考了个四边形的费马点,但是我们悲剧的卡在了Wron[......]

继续阅读

POJ 2777 Count Color 线段树

2010年10月26日 6 条评论

最近,搞完这个,就复习其他数据结构。这个题想了好久,知道用线段树,却不知道怎么解题。最后看了数据结构书才搞出来。就是给节点设置一个cover域,cover为0代表线段存在多种颜色,非零,代表纯色,数值用于区别颜色种类。
第一次建树时,根节点cover域为1。以后要涂色的时候,先看涂色区域是否覆盖当前节点的范围,如果覆盖,直接更改当前节点的cover域。否则,先看当前节点是否为纯色,如果是纯色,就要把纯色信息传递给左右子树,而当前节点cover域则变为0.表明当前节点覆盖的颜色不在是纯色,这样照着[......]

继续阅读