最近玩了一款手游拜隧，是一筆畫的內(nèi)容西傀，突然又想起來小時(shí)候...哈哈瞬間很懷念有木有动猬，小時(shí)候?qū)@樣的游戲也癡迷到不行虏束。
*不過長(zhǎng)大了玩游戲的心情都不一樣了棉饶，程序員做久了就非得想從里面找規(guī)律...這不還真的發(fā)現(xiàn)了一些小規(guī)律，然后游戲就瞬間變得無聊了起來镇匀。
以下是四個(gè)比較有用的結(jié)論↓↓↓
1.只有2個(gè)分支的節(jié)點(diǎn)可以被簡(jiǎn)化為一條線
這個(gè)圖再熟悉不過了吧照藻，怎么畫就不用多說了吧？0->2->4->1->3->0（呵呵程序員不從0開始對(duì)不起自己）
這個(gè)圖其實(shí)就是典型的可以按2個(gè)分支的節(jié)點(diǎn)來化簡(jiǎn)汗侵，0-2-4路徑上只有2一個(gè)節(jié)點(diǎn)幸缕，所以可以將2忽略掉，變成0->4,腦海中的畫面就變成了這個(gè)樣子：
繼續(xù)化簡(jiǎn)晰韵，0-4-1中4又可以忽略掉发乔，那么0->1又出來了...這時(shí)簡(jiǎn)化成什么了？怎么畫就不用說了吧雪猪！
2.孤島可以簡(jiǎn)化成一個(gè)節(jié)點(diǎn)來處理栏尚，前提是經(jīng)過節(jié)點(diǎn)是就要遍歷它
圖中0,1,2形成了一個(gè)孤島（姑且這么叫吧），3只恨，4译仗，5形成一個(gè)孤島，6官觅，7,8形成一個(gè)孤島纵菌，9,10,11形成一個(gè)孤島，當(dāng)我們經(jīng)過孤島節(jié)點(diǎn)比如1時(shí)我們就要優(yōu)先去遍歷他的孤島休涤，比如1->0->1->1這樣對(duì)整個(gè)圖的路徑?jīng)]有任何影響咱圆，圖就可以簡(jiǎn)化成如下的樣子：
簡(jiǎn)單了吧？
3.若以偶數(shù)節(jié)點(diǎn)為開始必然也以該偶數(shù)節(jié)點(diǎn)為結(jié)束功氨，反過來以偶數(shù)節(jié)點(diǎn)未結(jié)束意味著它一定是起點(diǎn)
上面的圖中序苏，假如我們以節(jié)點(diǎn)0開始，因?yàn)?是偶數(shù)節(jié)點(diǎn)疑故，那么我們的一筆畫也將以節(jié)點(diǎn)0結(jié)束杠览。
至于原因嘛弯菊，也很簡(jiǎn)單纵势。我們假如從0開始向1劃線踱阿，那么一筆畫的路徑如下圖:
偶數(shù)節(jié)點(diǎn)之所以要達(dá)到偶數(shù)，那么它必須一進(jìn)一出一進(jìn)一出扒仗软舌！
由此，便引出了我們最常用也最有效的結(jié)論↓↓↓
4.一個(gè)閉合的圖形中必然只包含0個(gè)或者2個(gè)奇數(shù)邊節(jié)點(diǎn)牛曹。
這個(gè)結(jié)論非常重要７鸬恪！黎比！
絕大多數(shù)圖要從這個(gè)結(jié)論入手３！阅虫！
原因也很簡(jiǎn)單演闭，也是上面的一進(jìn)一出。要證明它也很簡(jiǎn)單
首先我們假設(shè)一個(gè)包含2N + 1條邊的節(jié)點(diǎn)颓帝，我們分兩種情況討論：
1.以該節(jié)點(diǎn)畫起米碰，那么從我們一進(jìn)一出來看，經(jīng)過節(jié)點(diǎn)的路線必然是：
出->進(jìn)->出->進(jìn)......出->進(jìn)->出->進(jìn)......這個(gè)過程有N次出和N次進(jìn)购城，再一次回到了該節(jié)點(diǎn)吕座。那么此時(shí)該節(jié)點(diǎn)就只含有一條邊可以出去了，所以該節(jié)點(diǎn)必然不是一筆畫的終點(diǎn)瘪板。我們需要接盤俠...
從性質(zhì)2來看吴趴，任何一個(gè)偶數(shù)節(jié)點(diǎn)都不會(huì)當(dāng)接盤俠，人家成雙入對(duì)侮攀，一進(jìn)一出史侣。那么我們只能猜想接盤俠應(yīng)該也是一個(gè)奇數(shù)節(jié)點(diǎn)。下面我們來討論情況2魏身，看看奇數(shù)節(jié)點(diǎn)愿不愿意做接盤俠...
2.如果某個(gè)奇數(shù)節(jié)點(diǎn)不是起點(diǎn)惊橱，那么可以想象經(jīng)過它的路徑必然是是：
進(jìn)->出->進(jìn)->出...進(jìn)->出->進(jìn)->出...經(jīng)過N次進(jìn)和N次出，該節(jié)點(diǎn)還剩下一條路徑箭昵，并且路徑已經(jīng)出去了税朴，最后只能是由它來接盤了有木有！想再往外拋也沒地拋了有木有家制！這盤不接也得接啊...
從以上的2點(diǎn)論證我們可以得出結(jié)論正林，若圖中存在一個(gè)奇數(shù)節(jié)點(diǎn)就必然存在另一個(gè)奇數(shù)節(jié)點(diǎn)來接盤，因?yàn)榕紨?shù)點(diǎn)不肯接颤殴。如果存在大于2個(gè)奇數(shù)點(diǎn)將造成其他奇數(shù)點(diǎn)無盤可接的尷尬觅廓。所以奇數(shù)點(diǎn)必然不會(huì)大于2個(gè)。所以奇數(shù)點(diǎn)的個(gè)數(shù)要么是0要么是2涵但，而且是2時(shí)必然是一個(gè)起點(diǎn)一個(gè)終點(diǎn)杈绸。
OKＬ！瞳脓！由以上幾個(gè)結(jié)論我們基本就可以無腦游戲了
1.第一步尋找圖中有無奇數(shù)節(jié)點(diǎn)塑娇，如果有，找出這對(duì)奇數(shù)節(jié)點(diǎn)并從某個(gè)奇數(shù)節(jié)點(diǎn)開始畫起2.如果沒有奇數(shù)節(jié)點(diǎn)劫侧，那么任意一個(gè)偶數(shù)節(jié)點(diǎn)都可以當(dāng)成起始點(diǎn)埋酬，當(dāng)然選擇邊比較多的節(jié)點(diǎn)更容易畫。
OK烧栋，我們還是來舉幾個(gè)栗子吧：
以下是我總結(jié)的無法被一筆畫成的情形写妥，可以來坑隊(duì)友，哈哈审姓，給他出個(gè)難題耳标。
1.任何閉合圖形如果存在的奇數(shù)邊節(jié)點(diǎn)不是0個(gè)或者2個(gè)都無法被都無法被一筆畫成
2.任意包含大于2條非閉合邊的圖形無法被一筆畫成
3.包含2個(gè)節(jié)點(diǎn)的非閉合圖形次坡，簡(jiǎn)化后的閉合圖形起始和終止節(jié)點(diǎn)必然落在2個(gè)奇數(shù)邊節(jié)點(diǎn)上，否則無法被一筆畫成
特殊情況
當(dāng)某些復(fù)雜的情況下要求某個(gè)邊要多次經(jīng)過時(shí)可以按照經(jīng)過的次數(shù)算節(jié)點(diǎn)的維度画畅，還有某些邊要求特定方向通過砸琅，比較復(fù)雜，我們下次再分解轴踱。
