问题描述
• 当下面的情况满足时,
认为两个游戏卡片之间有一条路径相连:
• 路径只包含水平或者竖直的直线段
• 路径不能穿过别的游戏卡片
• 但是允许路径临时的离开矩形板
poj1054 讨厌的青蛙
题意:在一个row*col的矩阵里,留了n个青蛙的脚印。已知每只青蛙的步长是一定的,且都是从一个边界外,跳到了另一边的边界外,而且跳的是直线。每跳落地就留一个脚印在那个格子。现在问你那只在地里留下最多脚印的青蛙留下了多少只脚印(只要有可能就好)。
思路
首先针对 x 从小到大排序,然后枚举,这样为后面的剪枝提供了方便;
2.对于剪枝,因为题目中明确说了:青蛙是从外面跳进来,至少踩了 3 个黑点,然后跳出去的,于是可以加下面剪枝:a. 确定 2 点之间的间距之后,确定出发点之前的那个点是否在稻田外面,如果不是则剪枝;
b. 根据当前最优情况,确定当前的点只要要走多少步才能找到一个更优解,相当于是一个启发式的剪枝;
例题7-8 Fill倒水问题
题意:三个杯子容量分别为a,b,c,现在c是满的,a和b是空的,两个杯子 i 向 j 倒水,要么 i 倒完了 j 还没满,要么 j 满了 i 还有剩余,问达到某个杯子水量为d时总共倒得最小水量是多少?如果不能达到d,找一个小于d并且离d最近的一个解。
思路:倒水问题,但题目要求的是总的到水量,所以在bfs时到达过的状态还要检查更新,可能当前我确实到达d了用了sum水量,但可能后面还有比sum更小的解。
201612-1 中间数
问题描述
在一个整数序列a1, a2, …, an中,如果存在某个数,大于它的整数数量等于小于它的整数数量,则称其为中间数。在一个序列中,可能存在多个下标不相同的中间数,这些中间数的值是相同的。
POJ1222 熄灯问题
问题描述
一个由按钮组成的矩阵,其中每行有6个按钮,共5行。每个按钮的位置上有一盏灯。当按下一个按钮后,该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即,如果灯原来是点亮的,就会被熄灭;如果灯原来是熄灭的,则会被点亮。在矩阵角上的按钮改变3盏灯的状态;在矩阵边上的按钮改变4盏灯的状态;其他的按钮改变5盏灯的状态。
POJ1077 八数码问题(bfs)
八数码问题 ,单向广搜
八数码问题:
由1,2,3,4,5,6,7,8,x组成一个3*3的矩阵,如
1 2 3
4 x 5
6 7 8
其中x可与其上,下,左,右相邻的元素互换,
现问从给出状态出发到达以下状态:
1 2 3
4 5 6
7 8 x
需要对x进行怎样的位移操作,输出x的最少位移信息,
若状态不可达,输出unsolvable
uva839 天平问题
题意:天平的两端,每端的重量 wl 和 wr ,每端到中点的距离 dl 和 dr ,要满足wldl==wrdr才能保持天平平衡。天平的每端可以再系一个天平,该端的重量为该子天平的总重量。问最终天平是否能平衡。
给你一个杠杆两端的物体的质量和力臂,如果质量为零,则下面是一个杠杆,判断是否所有杠杆平衡