经典搜索问题，主要是时间上的优化，我用了三个辅助数组记录信息 row[i][k] = 1表示第i行数字k已经被使用，col[j][k] = 1表第j列数字k已经被使用，blo[i][k]表示第i个小九宫格中数字k已经被使用
还有很重要的一个优化（没有优化的话可能会超时，或者非常慢，像POJ讨论区里有很多说正着搜超时，倒着搜0ms，这的确是一个可以用的方法，但是有一定的随机性），每次填数字时，先扫描一遍整个矩阵，找出可选数字情况最少的那个0所在的地方，优先填这里，这样会使得搜索树尽可能的“瘦“一些，效果会非常明显
代码
1 | /* |
利用windows的API，FindFirstFile和FileNextFile，采用递归遍历指定文件夹中的所有文件及文件夹，第一次windows编程，代码写的很臃肿难看，请大家多多包涵！
1 |
|
我的当前目录下的test文件夹有“haha”文件夹以及test.1 , test , 2 , test , 3三个文件,”haha”文件夹里又含有“ai”文件夹以及haha.1 , haha.2 , haha.3三个文件，“ai”文件夹里又含有“wo”文件夹以及ai.1 , ai.2 , ai.3三个文件，”wo”文件夹里有wo.1 , wo.2 , wo.3三个文件。。。
程序输出结果：
1 | =========haha========== |
介绍：二叉排序树是以一定的规则排列树中元素，因而可以进行快速的排序和查询的树状数据结构，一般规则是：对于树中任意一个节点，左孩子严格小于根，根严格小于右孩子，有点像大根堆。（只是大根堆中左右孩子关系并不确定，且和根的关系是统一的，而且有上浮和下沉操作使得大根堆总是一棵完全二叉树，其不断弹出堆顶形成有序列的过程叫做堆排序。虽然二叉排序树中也有旋转操作使得树尽量平衡，但是由于数值大小分明的左右孩子，在进行平衡操作时远不如大根堆方便快捷。）对于一棵已经构造完成的排序二叉树，它的中序遍历序列即为升序排列的有序列，这就是二叉排序树的排序方法。
基本操作：二叉排序树的基本操作为查找、插入和删除。查找操作以及插入操作过程同二分查找类似，用待处理节点和当前节点进行数值比较，如果待处理节点的值小于当前节点的值，则进入当前节点的左子树进行操作，否则进入当前节点的右子树进行操作，直到到达叶子节点或者操作完成。删除操作有好几种实现方法，我是用的是“替罪羊节点法”，即从待删除节点的左子树中找到最大的一个节点（即“替罪羊节点”），用它的值覆盖待删除节点的值，然后删除替罪羊节点即可。在具体操作中还有许多需要注意的细节，在代码注释中有详细介绍。
一些想法：在最初的代码实现中，曾使用静态树，因为考虑到在处理大型数据时，重复的new或者malloc操作会使得程序慢的令人发指（并不是说指针慢，只是申请空间的过程耗费时间），所以一开始就开一段长度合适的空间，另外设置一个指针指示当前数组中可以用的节点，然后new操作在这里的实现就可以这样写：tmp->lc = &Tree[++index]，如果当前序列空间不够时，再用malloc或new申请另一段空间，有点类似内存池的概念。这样的静态操作经在线评测系统（POJ）测试，在进行最基本的操作来处理100，000左右的数据量时会快上两个甚至更多的数量级。静态树的查找和插入操作都可以正常进行，但是在进行删除操作时，我自己写的回收空间算法（为了节省空间，删除的节点重新归到可用空间中，想法是把待删除节点和当前排序树二叉树用的最后一个节点进行交换，再把上文提到的指针前移一位即可，代码实现可以写成：swap(*tmp , Tree[index–])。）总是不能正确执行，调了一段时间未果就先放在一边，写现在这个用指针操作实现的排序二叉树。
代码：（内置测试数据，并对于测试数据保证代码正确）
1 |
|
题意：轨道网，有若干转换器，每个转换器都和其他若干转换器相连，转换器初始指向第一个与其相连的转换器。问要到达终点需要最少转换多少次？
思路：可以用dijkstra单源最短路来做，把轨道网看做有向图（因为1第一个指向2，2的第一个不一定指向1），当前转换器处始指向的那个转换器之间的路径权值为0，其他路径权值为1，求一次起点到终点的最短路，结果就是最少转换次数，注意可能没有路径，这时要输出-1
代码：
1 | /* |
裸 dijkstra
思路：以x为源点，求到其他点的最短路，之后把邻接矩阵转置，再求一次x源
点的最短路，这样就一次是来的，一次是走的，相加迭代最大值即可
代码：
1 | /* |
题意很好理解就不说了，然后这道题其实不用字典树更简单，但是为了练习trie树就写了一下，1A了哈哈，再对比了一下讨论区的大神代码，发现我还是写复杂了。。。
思路：
想到利用字典树，继承字典树原有机制，从底端叶子向上找，每条路径最先找
到的分叉点再往下（从叶子找上来的这条路）一个字符即为所求（特殊情况，
如果节点处单词已结束，那么就输出整个单词好了），也就是从上往下找到的
第一个不是路径重合（has_same_path = true）的情况或者是is_word =
true的情况，用遍历二叉树的方法遍历整个树得到所有前缀。
判断has_same_path的情况很简单，如果当前tmp->next[num]不为空，则
一定has_same_path
，至于pos则是为了让答案按顺序输出用的
代码：
1 | /* |
其实空间没必要开那么大，为了省事就乱开了
version 1
从右到左排序，每次都尽可能的选打击范围内最右边的点安装雷达（由于浮点，所以不要一棒子打死的判断是大是小，给出一个精度范围，一开始范围给打了就WA），拿这个雷达去覆盖其他点，最后雷达总数一定是最少的
1 | /* |
version 2
找到以每个岛为圆心的圆与x轴左右交点形成一个区间，按左端点关键字升序排序后，用右端点去覆盖之后的点（如果遇到更小的右端点应该把目前的点更新），遇到不能覆盖的就雷达数目+1
1 | /* |
一开始用的DFS，无限TLE，贴丑代码
1 | //version 1 TLE |
之后冥思苦想了好久，两个序列，开始没有想到变形的LCS（最长公共子序列），只是试着写状态转移方程，最后就写成了那个dp[i][j] = max(dp[i-1][j-1] `,dp[i-1][j]`````,dp[i][j-1])的样子，这时一看才明白这是LCS思想，但是一开始确实是瞎写的，可能碰巧了吧=。=，最后注意这种情况:dp[0][x]，当一个序列之前都用0补上的话，在循环过程中是没办法得到结果的，只能预先处理，切记！
1 | /* |
Prim 最小生成树模板，直接上代码
1 | /* |
字典树，就是一种最大限度的利用单词的公共前缀高效查询单词（但不止是单词，所有有前缀的都可以类似进行查找）的数据结构。节点定义如下：
1 | struct node |
建树和查询都非常方便，删除操作并不常用，比较偷懒的方法就是找到待删除单词的最后一个字母所在节点，把isWord标记置为false即可。代码就不给出了。
需要注意的是，在实际建树过程中，如果动态分配空间无论是new还是malloc都会很慢，一般都会TLE的，所以代码都是静态实现，即先分配一定的空间，需要用新节点时就从空间里拿。
例题:
一、POJ 2503 Babelfish
1 | /* |
二、POJ 3630、Phone List
1 | /* |