演算法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等人提出。活動輪廓法邊緣檢測認為圖像中各區域的輪廓線應為平滑曲線，各輪廓線的能量由內部能量及外部能量（包括圖像能量及控制能量）兩部分組成，其中內部能量表徵了輪廓線的光滑約束，圖像能量由輪廓線上對應點的灰度、梯度和角點曲率半徑（若該點為角點）等決定，而控制能量則代表了圖像平面上固定點對輪廓線的吸引或排斥作用。採用變分法求解該能量函數的極小值就可得到與區域邊界相對應的輪廓線。