Codeforces Round #345 (Div. 1) C. Table Compression

原题C. Table Compressiotime limit per tes4 secondmemory limit per tes256 megabyteinpustandard inpuoutpustandard outpuLittle Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithms and many others. Inspired by the new knowledge, Petya is now developing the new compression algorithm which he wants to name dis.Petya decided to compress tables. He is give... Read More

深度优先搜索之栈解迷宫(C++)

在之前的一篇关于搜索的文章中《广度优先搜索算法队解迷宫问题》有提到深度优先搜索(dfs)算法,其中有一种就是本篇文章提到的实现方法:利用栈解迷宫;《广度优先搜索算法队解迷宫问题》中利用栈解迷宫有一个bug,比如:在x点出发,向右走直到尽头回到x点,此时在向其他方向(比如上),那么不能再走曾经向右走过的路(坐标)。这次,我们增加一个direct_mark数组,来标记在每一个坐标上曾经走过的方向。程序范例[code lang="cpp"/** 栈解迷宫 - 深度优先搜索.* @authur genialx <admin@ihuxu.com>*#include <iostr#include <st#define LEFT #define RIGHT #define UP #define DOWN using namespace std;struct Path int x;... Read More

广度优先搜索算法队解迷宫问题

面对迷宫问题,求解路径一共有三种方式。分别为:栈解迷宫(深度优先搜索)、递归法(深度优先搜索)与本文提到的队解迷宫(广度优先搜索),有兴趣可以参阅这篇文章。其中,栈指的是堆栈,队指的是队列。搜索中,利用了其堆栈的先进后出和队列的先进先出的特性。其中,前两种算法无法直接求出最短路径,而广度优先搜索会直接求出其最短路径。下面来具体讨论下队解迷宫的问题。问题这个迷宫问题的解答,主要参考了《LINUX一站式编程》中的第12章“栈与队列”的正文和习题。假设有这样一个迷宫,用一个5*5的数组来表示,其中0表示有路可走,1表示无路可走。那么,如何找到一个通路,使得可以从左上角的(0,0)点走到右下角的(4,4)点?迷宫搜索过程其中2代表已经走过的路,故观察2的覆盖流程即算法的运行流程。2 1 0 0 2 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 *********... Read More