算法snake
Ⅰ pasal题目
2003年国家集训队论文，王知昆，浅谈用极大化思想解决最大子矩形问题
网上有的，O(n²)的复杂度，n，m是5000都能1秒出解
浅谈用极大化思想解决最大子矩形问题
福州第三中学 王知昆
【摘要】
本文针对一类近期经常出现的有关最大（或最优）子矩形及相关变形问题，介绍了极大化思想在这类问题中的应用。分析了两个具有一定通用性的算法。并通过一些例题讲述了这些算法选择和使用时的一些技巧。
【关键字】 矩形，障碍点，极大子矩形
【正文】
一、 问题
最大子矩形问题：在一个给定的矩形网格中有一些障碍点，要找出网格内部不包含任何障碍点，且边界与坐标轴平行的最大子矩形。
这是近期经常出现的问题，例如冬令营2002的《奶牛浴场》，就属于最大子矩形问题。
Winter Camp2002,奶牛浴场
题意简述：（原题见论文附件）
John要在矩形牛场中建造一个大型浴场，但是这个大型浴场不能包含任何一个奶牛的产奶点，但产奶点可以出在浴场的边界上。John的牛场和规划的浴场都是矩形，浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。要求所求浴场的面积尽可能大。
参数约定：产奶点的个数S不超过5000,牛场的范围N×M不超过30000×30000。
二、 定义和说明
首先明确一些概念。
1、 定义有效子矩形为内部不包含任何障碍点且边界与坐标轴平行的子矩形。如图所示，第一个是有效子矩形（尽管边界上有障碍点），第二个不是有效子矩形（因为内部含有障碍点）。
2、 极大有效子矩形：一个有效子矩形，如果不存在包含它且比它大的有效子矩形，就称这个有效子矩形为极大有效子矩形。（为了叙述方便，以下称为极大子矩形）
3、 定义最大有效子矩形为所有有效子矩形中最大的一个（或多个）。以下简称为最大子矩形。
三、 极大化思想
【定理1】在一个有障碍点的矩形中的最大子矩形一定是一个极大子矩形。
证明：如果最大子矩形A不是一个极大子矩形，那么根据极大子矩形的定义，存在一个包含A且比A更大的有效子矩形，这与“A是最大子矩形”矛盾，所以【定理1】成立。
四、 从问题的特征入手，得到两种常用的算法
定理1虽然很显然，但却是很重要的。根据定理1，我们可以得到这样一个解题思路：通过枚举所有的极大子矩形，就可以找到最大子矩形。下面根据这个思路来设计算法。
约定：为了叙述方便，设整个矩形的大小为n×m，其中障碍点个数为s。
算法1
算法的思路是通过枚举所有的极大子矩形找出最大子矩形。根据这个思路可以发现，如果算法中有一次枚举的子矩形不是有效子矩形、或者不是极大子矩形，那么可以肯定这个算法做了“无用功”，这也就是需要优化的地方。怎样保证每次枚举的都是极大子矩形呢，我们先从极大子矩形的特征入手。
【定理2】：一个极大子矩形的四条边一定都不能向外扩展。更进一步地说，一个有效子矩形是极大子矩形的充要条件是这个子矩形的每条边要么覆盖迹消陪了一个障碍点，要么与整个矩形的边界重合。
定理2的正确性很显然，如果一个有效子矩形的某一条边既没有覆盖一个障碍点，又没有与整个矩形的边界重合，那么肯定存在一个包含它的有效子矩形。根据定理2，我们可姿蠢以得到一个枚举极大子矩形的算法。为了处理方便，首先在障碍点的集合中加上整个矩形四角上的点。每次枚举子矩形的上下左右边界（枚举覆盖的障碍点），然后判断是否合法（内部是否有包含障碍点）。这样的算法时间复杂度为O(S5)，显然太高了。考虑到极大子矩形不能包含障碍点，因此这样枚举4个边界显然会产生大量的无效子矩形。
考虑只枚举左右边界的情况。对于已经确定的左右边界，可以将所有处在这个边界内的点按从上到下排序，如图1中所示，每一格就代表一个有效子矩形。这样做时间复杂度为O(S3)。由于确保每次得到的矩形都是合法的，所以枚举量比前一种算法小了很多。但需要注意的是，这样做枚举的子矩形虽然是合法的，然而不一定是极大的。所以这个算法还有优化的余地。通过对这个算法不足之处的优化，我们可以得到一个高效的算法。
回顾上面的算法，我们不难发现，所枚举的矩形的上下边界都覆盖了障碍点或者与整个矩形的边界重合，问题就在于左右边界上。只有那些左右边界也覆盖了障碍点或者与整个矩形的边界重合的有效子矩形才是我们需要考察的极大子桥宽矩形，所以前面的算法做了不少“无用功”。怎么减少“无用功”呢，这里介绍一种算法（算法1），它可以用在不少此类题目上。
算法的思路是这样的，先枚举极大子矩形的左边界，然后从左到右依次扫描每一个障碍点，并不断修改可行的上下边界，从而枚举出所有以这个定点为左边界的极大子矩形。考虑如图2中的三个点，现在我们要确定所有以1号点为左边界的极大矩形。先将1号点右边的点按横坐标排序。然后按从左到右的顺序依次扫描1号点右边的点，同时记录下当前的可行的上下边界。
开始时令当前的上下边界分别为整个矩形的上下边界。然后开始扫描。第一次遇到2号点，以2号点作为右边界，结合当前的上下边界，就得到一个极大子矩形（如图3）。同时，由于所求矩形不能包含2号点，且2号点在1号点的下方，所以需要修改当前的下边界，即以2号点的纵坐标作为新的下边界。第二次遇到3号点，这时以3号点的横坐标作为右边界又可以得到一个满足性质1的矩形（如图4）。类似的，需要相应地修改上边界。以此类推，如果这个点是在当前点（确定左边界的点）上方，则修改上边界；如果在下方，则修改下边界；如果处在同一行，则可中止搜索（因为后面的矩形面积都是0了）。由于已经在障碍点集合中增加了整个矩形右上角和右下角的两个点，所以不会遗漏右边界与整个矩形的右边重合的极大子矩形（如图5）。需要注意的是，如果扫描到的点不在当前的上下边界内，那么就不需要对这个点进行处理。
这样做是否将所有的极大子矩形都枚举过了呢？可以发现，这样做只考虑到了左边界覆盖一个点的矩形，因此我们还需要枚举左边界与整个矩形的左边界重合的情况。这还可以分为两类情况。一种是左边界与整个举行的左边界重合，而右边界覆盖了一个障碍点的情况，对于这种情况，可以用类似的方法从右到左扫描每一个点作为右边界的情况。另一种是左右边界均与整个矩形的左右边界重合的情况，对于这类情况我们可以在预处理中完成：先将所有点按纵坐标排序，然后可以得到以相邻两个点的纵坐标为上下边界，左右边界与整个矩形的左右边界重合的矩形，显然这样的矩形也是极大子矩形，因此也需要被枚举到。
通过前面两步，可以枚举出所有的极大子矩形。算法1的时间复杂度是O(S2)。这样，可以解决大多数最大子矩形和相关问题了。
虽然以上的算法（算法1）看起来是比较高效的，但也有使用的局限性。可以发现，这个算法的复杂度只与障碍点的个数s有关。但对于某些问题，s最大有可能达到n×m，当s较大时，这个算法就未必能满足时间上的要求了。能否设计出一种依赖于n和m的算法呢？这样在算法1不能奏效的时候我们还有别的选择。我们再重新从最基本的问题开始研究。
算法2
首先，根据定理1：最大有效子矩形一定是一个极大子矩形。不过与前一种算法不同的是，我们不再要求每一次枚举的一定是极大子矩形而只要求所有的极大子矩形都被枚举到。看起来这种算法可能比前一种差，其实不然，因为前一种算法并不是完美的：虽然每次考察的都是极大子矩形，但它还是做了一定量的“无用功”。可以发现，当障碍点很密集的时候，前一种算法会做大量没用的比较工作。要解决这个问题，我们必须跳出前面的思路，重新考虑一个新的算法。注意到极大子矩形的个数不会超过矩形内单位方格的个数，因此我们有可能找出一种时间复杂度是O(N×M)的算法。
定义：
有效竖线：除了两个端点外，不覆盖任何障碍点的竖直线段。
悬线：上端点覆盖了一个障碍点或达到整个矩形上端的有效竖线。如图所示的三个有效竖线都是悬线。
对于任何一个极大子矩形，它的上边界上要么有一个障碍点，要么和整个矩形的上边界重合。那么如果把一个极大子矩形按x坐标不同切割成多个（实际上是无数个）与y轴垂直的线段，则其中一定存在一条悬线。而且一条悬线通过尽可能地向左右移动恰好能得到一个子矩形（未必是极大子矩形，但只可能向下扩展）。通过以上的分析，我们可以得到一个重要的定理。
【定理3】：如果将一个悬线向左右两个方向尽可能移动所得到的有效子矩形称为这个悬线所对应的子矩形，那么所有悬线所对应的有效子矩形的集合一定包含了所有极大子矩形的集合。
定理3中的“尽可能”移动指的是移动到一个障碍点或者矩形边界的位置。
根据【定理3】可以发现，通过枚举所有的悬线，就可以枚举出所有的极大子矩形。由于每个悬线都与它底部的那个点一一对应，所以悬线的个数＝(n-1)×m（以矩形中除了顶部的点以外的每个点为底部，都可以得到一个悬线，且没有遗漏）。如果能做到对每个悬线的操作时间都为O(1)，那么整个算法的复杂度就是O(NM)。这样，我们看到了解决问题的希望。
现在的问题是，怎样在O(1)的时间内完成对每个悬线的操作。我们知道，每个极大子矩形都可以通过一个悬线左右平移得到。所以，对于每个确定了底部的悬线，我们需要知道有关于它的三个量：顶部、左右最多能移动到的位置。对于底部为(i,j)的悬线，设它的高为hight[i,j],左右最多能移动到的位置为left[i,j],right[i,j]。为了充分利用以前得到的信息，我们将这三个函数用递推的形式给出。
对于以点(i,j)为底部的悬线：
如果点(i－1,j)为障碍点，那么，显然以(i,j)为底的悬线高度为1，而且左右均可以移动到整个矩形的左右边界，即
如果点(i－1,j)不是障碍点，那么，以(i,j)为底的悬线就等于以(i-1,j)为底的悬线＋点(i,j)到点(i-1,j)的线段。因此，height[i,j]=height[i-1,j]+1。比较麻烦的是左右边界，先考虑left[i,j]。如下图所示，(i,j)对应的悬线左右能移动的位置要在(i-1,j)的基础上变化。
即left[i,j]=max
right[i,j]的求法类似。综合起来，可以得到这三个参数的递推式：
这样做充分利用了以前得到的信息，使每个悬线的处理时间复杂度为O(1)。对于以点(i,j)为底的悬线对应的子矩形，它的面积为(right[i,j]-left[i,j])*height[i,j]。
这样最后问题的解就是：
Result＝
max
整个算法的时间复杂度为O(NM)，空间复杂度是O(NM)。
两个算法的对比：
以上说了两种具有一定通用性的处理算法，时间复杂度分别为O(S2)和O(NM)。两种算法分别适用于不同的情况。从时间复杂度上来看，第一种算法对于障碍点稀疏的情况比较有效，第二种算法则与障碍点个数的多少没有直接的关系（当然，障碍点较少时可以通过对障碍点坐标的离散化来减小处理矩形的面积，不过这样比较麻烦，不如第一种算法好），适用于障碍点密集的情况。
五、 例题
将前面提出的两种算法运用于具体的问题。
1、 Winter Camp2002,奶牛浴场
分析：
题目的数学模型就是给出一个矩形和矩形中的一些障碍点，要求出矩形内的最大有效子矩形。这正是我们前面所讨论的最大子矩形问题，因此前两种算法都适用于这个问题。
下面分析两种算法运用在本题上的优略：
对于第一种算法，不用加任何的修改就可以直接应用在这道题上，时间复杂度为O(S2)，S为障碍点个数；空间复杂度为O(S)。
对于第二种算法，需要先做一定的预处理。由于第二种算法复杂度与牛场的面积有关，而题目中牛场的面积很大（30000×30000），因此需要对数据进行离散化处理。离散化后矩形的大小降为S×S，所以时间复杂度为O(S2)，空间复杂度为O(S)。说明：需要注意的是，为了保证算法能正确执行，在离散化的时候需要加上S个点，因此实际需要的时间和空间较大，而且编程较复杂。
从以上的分析来看，无论从时空效率还是编程复杂度的角度来看，这道题采用第一种算法都更优秀。
2、 OIBH模拟赛1,提高组，Candy
题意简述：（原题见论文附件）
一个被分为 n*m 个格子的糖果盒，第 i 行第 j 列位置的格子里面有 a [i,j] 颗糖。但糖果盒的一些格子被老鼠洗劫。现在需要尽快从这个糖果盒里面切割出一个矩形糖果盒，新的糖果盒不能有洞，并且希望保留在新糖果盒内的糖的总数尽量多。
参数约定：1 ≤ n，m ≤ 1000
分析
首先需要注意的是：本题的模型是一个矩阵，而不是矩形。在矩阵的情况下，由于点的个数是有限的，所以又产生了一个新的问题：最大权值子矩阵。
定义：
有效子矩阵为内部不包含任何障碍点的子矩形。与有效子矩形不同，有效子矩阵地边界上也不能包含障碍点。
有效子矩阵的权值（只有有效子矩形才有权值）为这个子矩阵包含的所有点的权值和。
最大权值有效子矩阵为所有有效子矩阵中权值最大的一个。以下简称为最大权值子矩阵。
本题的数学模型就是正权值条件下的最大权值子矩阵问题。再一次利用极大化思想，因为矩阵中的权值都是正的，所以最大权值子矩阵一定是一个极大子矩阵。所以我们只需要枚举所有的极大子矩阵，就能从中找到最大权值子矩阵。同样，两种算法只需稍加修改就可以解决本题。下面分析两种算法应用在本题上的优略：
对于第一种算法，由于矩形中障碍点的个数是不确定的，而且最大有可能达到N×M,这样时间复杂度有可能达到O(N2M2)，空间复杂度为O(NM)。此外，由于矩形与矩阵的不同，所以在处理上会有一些小麻烦。
对于第二种算法，稍加变换就可以直接使用，时间复杂度为O(NM),空间复杂度为O（NM）。
可以看出，第一种算法并不适合这道题，因此最好还是采用第二种算法。
3、 Usaco Training, Section 1.5.4, Big Barn
题意简述（原题见论文附件）
Farmer John想在他的正方形农场上建一个正方形谷仓。由于农场上有一些树，而且Farmer John又不想砍这些树，因此要找出最大的一个不包含任何树的一块正方形场地。每棵树都可以看成一个点。
参数约定：牛场为N×N的，树的棵数为T。N≤1000,T≤10000。
分析：
这题是矩形上的问题，但要求的是最大子正方形。首先，明确一些概念。
1、 定义有效子正方形为内部不包含任何障碍点的子正方形
2、 定义极大有效子正方形为不能再向外扩展的有效子正方形，一下简称极大子正方形
3、 定义最大有效子正方形为所有有效子正方形中最大的一个（或多个），以下简称最大子正方形。
本题的模型有一些特殊，要在一个含有一些障碍点的矩形中求最大子正方形。这与前两题的模型是否有相似之处呢？还是从最大子正方形的本质开始分析。
与前面的情况类似，利用极大化思想，我们可以得到一个定理：
【定理4】：在一个有障碍点的矩形中的最大有效子正方形一定是一个极大有效子正方形。
根据【定理4】,我们只需要枚举出所有的极大子正方形，就可以从中找出最大子正方形。极大子正方形有什么特征呢？所谓极大，就是不能再向外扩展。如果是极大子矩形，那么不能再向外扩展的充要条件是四条边上都覆盖了障碍点（【定理2】）。类似的，我们可以知道，一个有效子正方形是极大子正方形的充要条件是它任何两条相邻的边上都覆盖了至少一个障碍点。根据这一点，可以得到一个重要的定理。
【定理5】：每一个极大子正方形都至少被一个极大子矩形包含。且这个极大子正方形一定有两条不相邻的边与这个包含它的极大子矩形的边重合。
根据【定理5】,我们只需要枚举所有的极大子矩形，并检查它所包含的极大子正方形（一个极大子矩形包含的极大子正方形都是一样大的）是否是最大的就可以了。这样，问题的实质和前面所说的最大子矩形问题是一样的，同样的，所采用的算法也是一样的。
因为算法1和算法2都枚举出了所有的极大子矩形，因此，算法1和算法2都可以用在本题上。具体的处理方法如下：对于每一个枚举出的极大子矩形，如图所示，如果它的边长为a、b，那么它包含的极大子正方形的边长即为min(a,b)。
考虑到N和T的大小不同，所以不同的算法会有不同的效果。下面分析两种算法应用在本题上的优略。
对于第一种算法，时间复杂度为O(T2)，对于第二种算法，时间复杂度为O(N2)。因为N<T，所以从时间复杂度的角度看，第二种算法要比第一种算法好。考虑到两个算法的空间复杂度都可以承受，所以选择第二种算法较好些。
以下是第一种和第二种算法编程实现后在USACO Training Program Gateway上的运行时间。可以看出，在数据较大时，算法2的效率比算法1高。
算法1：
Test 1: 0.009375
Test 2: 0.009375
Test 3: 0.009375
Test 4: 0.009375
Test 5: 0.009375
Test 6: 0.009375
Test 7: 0.021875
Test 8: 0.025
Test 9: 0.084375
Test 10: 0.3875
Test 11: 0.525
Test 12: 0.5625
Test 13: 0.690625
Test 14: 0.71875
Test 15: 0.75 算法2：
Test 1: 0.009375
Test 2: 0.009375
Test 3: 0.009375
Test 4: 0.009375
Test 5: 0.009375
Test 6: 0.00625
Test 7: 0.009375
Test 8: 0.009375
Test 9: 0.0125
Test 10: 0.021875
Test 11: 0.028125
Test 12: 0.03125
Test 13: 0.03125
Test 14: 0.03125
Test 15: 0.034375
以上，利用极大化思想和前面设计的两个算法，通过转换模型，解决了三个具有一定代表性的例题。解题的关键就是如何利用极大化思想进行模型转换和如何选择算法。
五、小结
设计算法要从问题的基本特征入手，找出解题的突破口。本文介绍了两种适用于大部分最大子矩形问题及相关变型问题的算法，它们设计的突破口就是利用了极大化思想，找到了枚举极大子矩形这种方法。
在效率上，两种算法对于不同的情况各有千秋。一个是针对障碍点来设计的，因此复杂度与障碍点有关；另一个是针对整个矩形来设计的，因此复杂度与矩形的面积有关。虽然两个算法看起来有着巨大的差别，但他们的本质是相通的，都是利用极大化思想，从枚举所有的极大有效子矩形入手，找出解决问题的方法。
需要注意的是，在解决实际问题是仅靠套用一些现有算法是不够的，还需要对问题进行全面、透彻的分析,找出解题的突破口。
此外，如果采用极大化思想，前面提到的两种算法的复杂度已经不能再降低了，因为极大有效子矩形的个数就是O(NM)或O(S2)的。如果采用其他算法，理论上是有可能进一步提高算法效率，降低复杂度的。
七、 附录：
1、几个例题的原题。 见论文附件.doc
2、例题的程序。 见论文附件.doc
说明：所有程序均在Free Pascal IDE for Dos, Version 0.9.2上编译运行
参考书目
1、 信息学奥林匹克 竞赛指导
----1997～1998竞赛试题解析
吴文虎 王建德 着
2、 IOI99中国集训队优秀论文集
3、 信息学奥林匹克（季刊）
4、 《金牌之路 竞赛辅导》
江文哉主编 陕西师范大学出版社出版
Ⅱ 求snake算法的实现详解
我也正在研究，希望高手指导一下吧，看了一周的论文了，继续研究中
Ⅲ matlab中snake算法的snakedeform函数的参数设置
你看看你的x,y的大小，应该是维数不符合。。。不过别人也没你的snakedeform函数，所以也无从帮起
Ⅳ c语言贪吃蛇怎么让蛇自己动起来啊
#define N 200
#include <graphics.h>
#include <stdlib.h>
#include <dos.h>
#define LEFT 0x4b00
#define RIGHT 0x4d00
#define DOWN 0x5000
#define UP 0x4800
#define ESC 0x011b
int i,key;
int score=0;/*得分*/
int gamespeed=50000;/*游戏速度自己调整*/
struct Food
{
int x;/*食物的横坐标*/
int y;/*食物的纵坐标*/
int yes;/*判断是否要出现食物的变量*/
}food;/*食物的结构体*/
struct Snake
{
int x[N];
int y[N];
int node;/*蛇的节数*/
int direction;/*蛇移动方向*/
int life;/* 蛇的生命,0活着,1死亡*/
}snake;
void Init(void);/*图形驱动*/
void Close(void);/*图形结束*/
void DrawK(void);/*开始画孝猜面*/
void GameOver(void);/*结束游戏*/
void GamePlay(void);/*玩游戏具体过巧升型程*/
void PrScore(void);/*输出成绩*/
/*主函数*/
void main(void)
{
Init();/*图形驱动*/
DrawK();/*开始画面*/
GamePlay();/*玩游戏具体过程*/
Close();/*图形结束*/
}
/*图形驱动*/
void Init(void)
{
int gd=DETECT,gm;
initgraph(&gd,&gm,"笑薯c:\\tc");
cleardevice();
}
/*开始画面，左上角坐标为（50，40），右下角坐标为（610，460）的围墙*/
void DrawK(void)
{
/*setbkcolor(LIGHTGREEN);*/
setcolor(11);
setlinestyle(SOLID_LINE,0,THICK_WIDTH);/*设置线型*/
for(i=50;i<=600;i+=10)/*画围墙*/
{
rectangle(i,40,i+10,49); /*上边*/
rectangle(i,451,i+10,460);/*下边*/
}
for(i=40;i<=450;i+=10)
{
rectangle(50,i,59,i+10); /*左边*/
rectangle(601,i,610,i+10);/*右边*/
}
}
/*玩游戏具体过程*/
void GamePlay(void)
{
randomize();/*随机数发生器*/
food.yes=1;/*1表示需要出现新食物,0表示已经存在食物*/
snake.life=0;/*活着*/
snake.direction=1;/*方向往右*/
snake.x[0]=100;snake.y[0]=100;/*蛇头*/
snake.x[1]=110;snake.y[1]=100;
snake.node=2;/*节数*/
PrScore();/*输出得分*/
while(1)/*可以重复玩游戏,压ESC键结束*/
{
while(!kbhit())/*在没有按键的情况下,蛇自己移动身体*/
{
if(food.yes==1)/*需要出现新食物*/
{
food.x=rand()%400+60;
food.y=rand()%350+60;
while(food.x%10!=0)/*食物随机出现后必须让食物能够在整格内,这样才可以让蛇吃到*/
food.x++;
while(food.y%10!=0)
food.y++;
food.yes=0;/*画面上有食物了*/
}
if(food.yes==0)/*画面上有食物了就要显示*/
{
setcolor(GREEN);
rectangle(food.x,food.y,food.x+10,food.y-10);
}
for(i=snake.node-1;i>0;i--)/*蛇的每个环节往前移动,也就是贪吃蛇的关键算法*/
{
snake.x[i]=snake.x[i-1];
snake.y[i]=snake.y[i-1];
}
/*1,2,3,4表示右,左,上,下四个方向,通过这个判断来移动蛇头*/
switch(snake.direction)
{
case 1:snake.x[0]+=10;break;
case 2: snake.x[0]-=10;break;
case 3: snake.y[0]-=10;break;
case 4: snake.y[0]+=10;break;
}
for(i=3;i<snake.node;i++)/*从蛇的第四节开始判断是否撞到自己了，因为蛇头为两节，第三节不可能拐过来*/
{
if(snake.x[i]==snake.x[0]&&snake.y[i]==snake.y[0])
{
GameOver();/*显示失败*/
snake.life=1;
break;
}
}
if(snake.x[0]<55||snake.x[0]>595||snake.y[0]<55||
snake.y[0]>455)/*蛇是否撞到墙壁*/
{
GameOver();/*本次游戏结束*/
snake.life=1; /*蛇死*/
}
if(snake.life==1)/*以上两种判断以后,如果蛇死就跳出内循环，重新开始*/
break;
if(snake.x[0]==food.x&&snake.y[0]==food.y)/*吃到食物以后*/
{
setcolor(0);/*把画面上的食物东西去掉*/
rectangle(food.x,food.y,food.x+10,food.y-10);
snake.x[snake.node]=-20;snake.y[snake.node]=-20;
/*新的一节先放在看不见的位置,下次循环就取前一节的位置*/
snake.node++;/*蛇的身体长一节*/
food.yes=1;/*画面上需要出现新的食物*/
score+=10;
PrScore();/*输出新得分*/
}
setcolor(4);/*画出蛇*/
for(i=0;i<snake.node;i++)
rectangle(snake.x[i],snake.y[i],snake.x[i]+10,
snake.y[i]-10);
delay(gamespeed);
setcolor(0);/*用黑色去除蛇的的最后一节*/
rectangle(snake.x[snake.node-1],snake.y[snake.node-1],
snake.x[snake.node-1]+10,snake.y[snake.node-1]-10);
} /*endwhile（！kbhit）*/
if(snake.life==1)/*如果蛇死就跳出循环*/
break;
key=bioskey(0);/*接收按键*/
if(key==ESC)/*按ESC键退出*/
break;
else
if(key==UP&&snake.direction!=4)
/*判断是否往相反的方向移动*/
snake.direction=3;
else
if(key==RIGHT&&snake.direction!=2)
snake.direction=1;
else
if(key==LEFT&&snake.direction!=1)
snake.direction=2;
else
if(key==DOWN&&snake.direction!=3)
snake.direction=4;
}/*endwhile(1)*/
}
/*游戏结束*/
void GameOver(void)
{
cleardevice();
PrScore();
setcolor(RED);
settextstyle(0,0,4);
outtextxy(200,200,"GAME OVER");
getch();
}
/*输出成绩*/
void PrScore(void)
{
char str[10];
setfillstyle(SOLID_FILL,YELLOW);
bar(50,15,220,35);
setcolor(6);
settextstyle(0,0,2);
sprintf(str,"score:%d",score);
outtextxy(55,20,str);
}
/*图形结束*/
void Close(void)
{
getch();
closegraph();
}
Ⅳ 贪吃蛇原理啥
1 控制部分 就是通过输入输出来控制蛇的运正答动
2 逻辑部分 进行判断蛇吃了没有 是否撞墙 同时把蛇的长度增运清激加旁袜一节 还要实现分数的计算
3 图象显示部分 就是将游戏显示出来
Ⅵ C语言贪吃蛇移动
for(i=snake.node-1;i>0;i--)/*蛇的每个环节往前移动,也就是贪吃蛇的关键算法*/
{
snake.x[i]=snake.x[i-1];
snake.y[i]=snake.y[i-1];
}
注释已经解释的很清楚了，不知道你还要问什么？
Ⅶ snake 算法的一点小问题
在调用KSVD之前加param.displayProgress=1;试试。不过我用KSVD算法得到的精确度比一般算法都低！
Ⅷ 跪求图像分割snake算法详细解释
主要公式为曲线能量Esnake(公式1)；Esnake由内部能量Eint(公式2)及外部能量Eext(公式3)组成；而根据公式2内部能量Eint是由一阶导得到的平滑性约束(弹性绳子)二阶导得到的气球约束(刚性棍子)共同决定；根据公式3外部能Eext由梯度场决定(另一个分量不考虑)那么粗略表示为Esnake=Vs+Vss+Eext；可以认为当Esnake的能量达到最小时snake曲线和物体的边缘一致。
上面这些基本是每个论文上面都有的，下面照我的理解来讲。结合很多论文上用的那个U形物体，snake检测它的轮廓时，预先以一个圆形的像素圈套住它作为初始的snake线，可以取一定个数的点来离散化snake线,那么这时就可以求这条snake线与原始图像间的曲线能量Esnake了；Vs对应的是一阶的平滑性，可转化为snake线中相邻像素之间的坐标差;差值越大能量越大平滑性也就越差；Vss对应的是二阶的刚性；可转化为snake线中某点和它相邻的线上点间的法线方向的增长度量;Eext是梯度场能量，是由原本的灰度图决定的，可转化为snake中某点在灰度图中的邻域梯度。求出了这三个；再以一定的方式进行循环逼近那个使Esnake最小的snake线就找到了轮廓。
过奖了~我也是在研究中，你留个邮箱，我发个程序给你，看实例好理解点
Ⅸ 如何实现snake算法的matlab编程,来提取图像中划痕缺陷的边缘，谁有程序不妨发上来
N = length(x);
alpha = alpha* ones(1,N);
beta = beta*ones(1,N);
% proce the five diagnal vectors
alpham1 = [alpha(2:N) alpha(1)];
alphap1 = [alpha(N) alpha(1:N-1)];
betam1 = [beta(2:N) beta(1)];
betap1 = [beta(N) beta(1:N-1)];
a = betam1;
b = -alpha - 2*beta - 2*betam1;
c = alpha + alphap1 +betam1 + 4*beta + betap1;
d = -alphap1 - 2*beta - 2*betap1;
e = betap1;
% generate the parameters matrix
A = diag(a(1:N-2),-2) + diag(a(N-1:N),N-2);
A = A + diag(b(1:N-1),-1) + diag(b(N), N-1);
A = A + diag(c);
A = A + diag(d(1:N-1),1) + diag(d(N),-(N-1));
A = A + diag(e(1:N-2),2) + diag(e(N-1:N),-(N-2));
invAI = inv(A + gamma * diag(ones(1,N)));
for count = 1:ITER,
vfx = interp2(fx,x,y,'*linear');
vfy = interp2(fy,x,y,'*linear');
% deform snake
x = invAI * (gamma* x + kappa*vfx);
y = invAI * (gamma* y + kappa*vfy);
end
Ⅹ 跪求图像分割snake算法详细解释_基于遗传算法的图像分割
这个不太熟悉，下面是转载，希望能帮到你：
图像分割有那些方法区别如何
图像分割有那些方法区别如何？
图像分割是图像处理领域中的一个基本问题。从大的方面来说，图像分割方法可大致分为基于区域的方法、基于边缘的方法、区域与边缘相结合的方法，以及在此基础上的、采用多分辨率图像处理理论的多尺度分割方法。基于区域的方法采用某种准则，直接将图像划分为多个区域，基于边缘的方法则通过检测包含不同区域的边缘，获得关于各区域的边界轮廓描述，达到图像分割的目的，而区域与边缘相结合的方法通过区域分割与边缘检测的相互作用，得到分割结果。
·1基于区域的图像分割兄旅蚂
图像分割中常用的直方图门限法、区域生长法、基于图像的随机场模型法、松弛标记区域分割法等均属于基于区域的方法。
（1）直方图门限分割就是在一定的准则下，用一个或几个门限值将图像的灰度直方图（一维的或多维的）分成几个类，认为图像中灰度值在同一个灰度类内的象素属于同一个物体，可以采用的准则包括直方图的谷底、最小类内方差（或最大类间方差）、最大熵（可使用各种形式的熵）、最小错误率、矩不变、最大繁忙度（由共生矩阵定义）等。门限法的缺陷在于它仅仅考虑了图像的灰度信息，而忽略了图像中的空间信息，对于图像中不存在明显的灰度差异或各物体的灰度值范围有较大重叠的图像分割问题难以得到准确的结果。
（2）区域生长是一种古老的图像分割方法，最早的区域生长图像分割方法是由Levine等人提出的。该方法一般有两种方式，一种是先给定图像中要分割的目标物体内的一个小块或者说种子区域，再在镇闷种子区域基础上不断将其周围的像素点以一定的规则加入其中，达到最终将代表该物体的所有像素点结合成一个区域的目的；另一种是先将图像分割成很多的一致性较强，如区域内像素灰度值相同的小区域，再按一定的规则将小区域融合成大区域，达到分割图像的目的，典型的区域生长法如T.C.Pong等人提出的基于小面（facet）模型的区域生长法，区域生长法固有的缺点是往往会造成过度分割，即将图像分割成过多的区域。
（3）基于图像的随机场模型法主要以Markov随机场作为图像模型，并假定该随机场符合Gibbs分布。使用MRF模型进行图像分割的问题包括：邻域系统的定义；能量函数的选择及其参数的估计；极小化能量函数从而获得最大后验概率的策略。邻域系统一般是事先定义的，因而主要是后面两个问题。S.Geman，首次将基于Gibbs分布的Markov随机场模型用于图像处理，详细讨论了MRF模型的邻域系统，能量函数，Gibbs采样方法等各种问题，提出用模拟退火算法来极小化能量函数的方法，并给出了模拟退火算法收敛性的证明，同时给出了MRF模型在图像恢复中的应用实例。在此基础上，人们提出了大量的基于MRF模型的图像分割算法。
（4）标记法（labeling）就是将图像欲分割成的几个区域各以一个不同的标号来表示，对图像中的每一个象素，用一定的方式赋之以这些标记中的某一个，标记相同的连通象素就组成该标记所代表的区域。标记法常采用松弛技术来给图像中的各个象素赋予标记，一般可分为离散松弛、概率松弛、模糊松弛等三种。Smith等人最先采用松弛标记技术进行图像分割，以后人们又提出了大量的图像松弛分割算法。另外，松弛标记不仅可用于图像分割，还可用于边缘检测、目标识别等。
·2基于边缘的图像分割
基于边缘的分割方法则与边缘检测理论紧密相关，此类方法大多是基于局部信息的，一般利用图像—阶导数的极大值或二阶导数的过零点信息来提供判断边缘点的基本依据，进一步还可以采用各种曲线拟合技术获得划分不同区域边界的连续曲线。根据检测边缘所采用的方式的不同，边缘检测方法可大致分为以下几类：基于局部图像函数的方法、图像滤波法、基于反应—扩散方程的方法、基于边界曲线拟合的方法及活动轮廊（activecontour）法等。
(1)基于局部图像函数羡埋法的基本思想是将灰度看成高度，用一个曲面来拟合一个小窗口内的数据，然后根据该曲面来决定边缘点.
(2)图像滤波法是基于如下理论的：即对滤波算子与图像的卷积结果求导，相当于用算子的同阶导数与图像做卷积。于是，只要事先给出算子的一阶或二阶导数，就可以将图像平滑滤波与对平滑后的图像求一阶或二阶导数在一步完成。因而，这种方法的核心问题是滤波器的设计问题。
常用的滤波器主要是高斯（Gaussian）函数的一阶和二阶层数，Canny认为高斯函数的一阶导数是他求得的最优滤波器的较好似近，一般采用Laplacian算子求高斯函数的二阶导数得到LOG(LaplacianofGaussian)滤波算子，该算子由计算机视觉的创始人Marr首先提出.近年来研究的滤波器还有可控滤波器（steerable），B-样条滤波器等。
问题提出：图像滤波的方法是基于对平滑滤波后的图像求其一阶导数的极大值或二阶导数的过零点来决定边缘的，必然遇到的问题是，一阶的极大值或二阶导数的过零点对应的像素点是否真的就是边缘点？
(3)基于反应—扩散方程的方法是从传统意义上的Gaussian核函数多尺度滤波来的。由于本人阅读文献有限，这里不多做介绍了。
(4)基于边界曲线拟合的方法用平面曲线来表示不同区域之间的图像边界线，试图根据图像梯度等信息找出能正确表示边界的曲线从而得到图像分割的目的，而且由于它直接给出的是边界曲线而不象一般的方法找出的是离散的、不相关的边缘点，因而对图像分割的后继处理如物体识别等高层处理有很大帮助。即使是用一般的方法找出的边缘点，用曲线来描述它们以便于高层处理也是经常被采用的一种有效的方式。L.H.Staib等人在文献中给出了一种用Fourier参数模型来描述曲线的方法，并根据Bayes定理，按极大后验概率的原则给出了一个目标函数，通过极大化该目标函数来决定Fourier系数。实际应用中，先根据对同类图像的分割经验，给出一条初始曲线，再在具体分割例子中根据像数据优化目标函数来改变初始曲线的参数，拟合图像数据，得到由图像数据决定的具体曲线。这种方法比较适合于医学图像的分割。除了用Fourier模型来描述曲线外，近年来还研究了一些其它的曲线描述方法，如A.Goshtasby详细介绍了用有理Gaussian曲线和曲面来设计和拟合二维及三维形状的方法。R.Legault等人给出了一种曲线平滑的方法。M.F.Wu等人给出了一种双变量三维Fourier描述子来描述三维曲面。
(5)活动轮廓（又称Snake模型）是一种可变形模型（或称弹性模型），最初由Kass等人提出。活动轮廓法边缘检测认为图像中各区域的轮廓线应为平滑曲线，各轮廓线的能量由内部能量及外部能量（包括图像能量及控制能量）两部分组成，其中内部能量表征了轮廓线的光滑约束，图像能量由轮廓线上对应点的灰度、梯度和角点曲率半径（若该点为角点）等决定，而控制能量则代表了图像平面上固定点对轮廓线的吸引或排斥作用。采用变分法求解该能量函数的极小值就可得到与区域边界相对应的轮廓线。