搜索 - xIao_wU 思维磁场 - Just Run And Never Forget I Have A Dream

HDU -- 3287 Theta Puzzle

    有7个点 , 可以给每个点编号 , 分别为0~6 , 故这个图共有 7! = 5040 种状态量,这个状态量可以很灵活的实现 , 而且要超时基本是不可能的 , 判重方面可以适用全排列的hash , 故内存也占极少 , 所以适用任何一种算法。
   状态转移则可以适用
   int move[7][3] = { {1 , 5} , {0 , 2 , 6} , {1 , 3} , {2 , 4} , {3 , 5 , 6} , {0 , 4} , {1 , 4} };
   若move[j] 则表示 i点和j点可互换 , i 点为这个游戏的空点。
   开多一个数组来存可以移动个数
   int dir[7] = {2 , 3 , 2 , 2 , 3 , 2 , 2};

继续阅读

PKU 3009 -- Curling 2.0

    刚开始毋庸置疑的敲了个BFS,想到可以轻轻松松过掉,发现样例过不了,怪怪的。细想一下,发现BFS中保存的vis数组中,若之前给碰掉的墙块就成为空的,将导致其他状态中也无视了这个块,若每个状态都要保存一个20 * 20的矩阵的话,空间消耗是可想而知的。故可以利用dfs的回溯,由于不用考虑最优值,只要找出步数小于10的即可,DFS恰好可以解决此题的空间问题。

    觉得这题挺不错的,之前做的,一直没有写出解题报告,前段日子太忙了 - -#

继续阅读




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee