兒童故事貪吃的蛇故事

答：貪吃蛇大作戰(zhàn)的游戲規(guī)則并不是大蛇吃小蛇，而是誰撞到別人誰就GG。玩過貪吃蛇的不會(huì)陌生，在蛇蛇大作戰(zhàn)中不管玩家有多大，只要是碰到別人，自己就會(huì)死亡。蛇蛇大作戰(zhàn)里的光點(diǎn)和光團(tuán)都是蛇蛇使自己變大的“食物”或者說是“能量團(tuán)”。

在玩貪吃蛇游戲的時(shí)候一個(gè)基本問題是如何能夠讓蛇不死。如果一個(gè)方法能夠讓貪吃蛇一直不死且能走到地圖上的任意位置，那么我們也就能夠得到一條最長的貪吃蛇。如：

貪吃蛇模型

在貪吃蛇游戲中，蛇每吃到一個(gè)蘋果，身體會(huì)變長。當(dāng)蛇撞到障礙物或者自己的身體時(shí)，則游戲結(jié)束。我們討論兩種平時(shí)玩的最多的貪吃蛇地圖模型，無墻地圖和有墻地圖。顧名思義，無墻模型中貪吃蛇走到地圖最邊上時(shí)能夠從地圖的另一側(cè)出來。

而有墻地圖中，撞墻則死。

在兩種模型中，找到不死貪吃蛇的關(guān)鍵是能找到一條遍歷圖上所有格子的環(huán)路，則沿著此環(huán)路行走，既能吃到所有的蘋果又不會(huì)和身體相撞。

無墻地圖中的不死貪吃蛇

在無墻的地圖中，根據(jù)地圖的行數(shù)為奇數(shù)還是偶數(shù)會(huì)有不同的走法。

最簡單的是行數(shù)（或者列數(shù)）為偶數(shù)的情況。假設(shè)行數(shù)為偶數(shù)，我們可以通過橫向掃描的方法找到一個(gè)遍歷所有點(diǎn)的環(huán)路。如圖

當(dāng)行數(shù)和列數(shù)都為奇數(shù)時(shí)，上面的方法不適用了，但我們在第一第二行執(zhí)行W型的行走，在其余行執(zhí)行橫向的掃描可以找到一條遍歷所有點(diǎn)的環(huán)路。如圖

有墻地圖中的不死貪吃蛇

有墻地圖中周圍的一圈墻使得上述的兩種方法不能直接適用。于是我們需要在圍墻之內(nèi)找到一條蛇的“回路”。

當(dāng)行數(shù)為偶數(shù)時(shí)，將第一列作為“回路”，我們可以得到一條遍歷所有格點(diǎn)的環(huán)路。如圖

當(dāng)行數(shù)和列數(shù)都為奇數(shù)時(shí)，似乎找不到一個(gè)遍歷所有格點(diǎn)的環(huán)路（未證明），但如果我們刪去一個(gè)點(diǎn)，如最左上角的點(diǎn)，則可以得到一個(gè)遍歷其他格點(diǎn)的環(huán)路。為了解決蘋果出現(xiàn)在最左上角的情況，我們找到2條路徑，它們唯一的差別是否經(jīng)過左上角的點(diǎn)。這兩條路徑能夠自由的切換。如圖。只有當(dāng)左上角的蘋果為最后一個(gè)格點(diǎn)時(shí)，蛇才會(huì)在吃完此蘋果后走入絕境。此時(shí)游戲判斷格子占滿，結(jié)束了。

快速貪吃蛇算法

不死貪吃蛇算法雖然最終能夠走遍所有格子，但時(shí)間復(fù)雜度非常高。假設(shè)地圖是n*n的，那么最壞情況下每吃一個(gè)果子，就要行走n^2個(gè)點(diǎn)。因?yàn)楣灿衝^2個(gè)果子，所以完成游戲需要經(jīng)歷n^4個(gè)格子。又在貪吃蛇游戲中蛇的行動(dòng)是勻速的，所以時(shí)間復(fù)雜度是O(n^4).

我們發(fā)現(xiàn)在不死貪吃蛇中，當(dāng)蛇的長度比較短時(shí)，很多路徑是沒有必要走的。蛇行走很長路徑是為了“消化”自己太長的身體。如果我們能夠根據(jù)蛇的身體長度和果子出現(xiàn)的位置，找到一些較短的回路，那么蛇吃到一個(gè)果子的時(shí)間就會(huì)縮短。一個(gè)自然的想法是每次尋找一個(gè)能吃到果子的最短的環(huán)路。我們提出一個(gè)基于最小環(huán)路的快速貪吃蛇算法（ShortestRing-Based Fast Snake）.

最小環(huán)路快速貪吃蛇算法

我們發(fā)現(xiàn)，通過添加回路，我們能夠從大的貪吃蛇環(huán)路上構(gòu)造出若干個(gè)小的環(huán)路。蛇沿著這些小的環(huán)路又能夠自由的進(jìn)入大的環(huán)路而不碰撞到自己的身體。這些小的環(huán)路要經(jīng)過果子，且長度至少是蛇的身長+1（吃了果子會(huì)變長）。并且小環(huán)和大環(huán)相交的地方走向要一致。如圖。

圖中灰色通道是我們添加的回路。我們發(fā)現(xiàn)，通過添加回路，我們能夠得到一些較小的環(huán)。繞著這些環(huán)行走，蛇能夠以較小的行動(dòng)路徑吃到一個(gè)果子。同時(shí)蛇又能夠自然的從小環(huán)路走到大環(huán)路中（圖上綠色虛線部分）。構(gòu)造小環(huán)路的方式不是唯一的，好的構(gòu)造方法能夠讓我們盡快的吃到果子。

考慮蛇吃完一個(gè)果子要走到下一個(gè)環(huán)路，可以找一條兩個(gè)環(huán)路間最短的路線。這條路線最長為行的個(gè)數(shù)n。

所以吃到一個(gè)果子的時(shí)間減少為（蛇身長+1+n）。通過求和，其時(shí)間復(fù)雜度雖然仍為O(n^4)但系數(shù)有所減少。

貪吃蛇1游戲是經(jīng)典手機(jī)游戲，既簡單又耐玩。通過控制蛇頭方向吃蛋，使得蛇碰嫌變長，從而獲得慧備積分。貪吃蛇鉆井測井技術(shù)是一種運(yùn)用旋轉(zhuǎn)導(dǎo)向系統(tǒng)、隨鉆測井系統(tǒng)等的油氣田定向鉆井、隨鉆測井技術(shù)，可前吵毀完成海上“叢式井”和復(fù)雜油氣層的開采需求，大幅降低油氣田開發(fā)綜合成本。