小車跑迷宮，如何完成？

要制作一個(gè)能順利走到迷宮終點(diǎn)，并能按最短路徑回來的小車，重中之重就是尋找其最短路徑的算法，迷宮情況復(fù)雜多變，多個(gè)路口交錯(cuò)縱橫，想要完美的找出最短路徑并不容易，我因此總結(jié)出一套算法，能迅速找出最短路徑，并適用于大多數(shù)迷宮情形，此算法對(duì)算力要求不高，不會(huì)過多阻礙主程序的運(yùn)行。

在小車去終點(diǎn)時(shí)，我們規(guī)定小車必須優(yōu)先左轉(zhuǎn)，其次直走，最后右轉(zhuǎn)，用暴力枚舉即可到達(dá)終點(diǎn)。在迷宮中，把每一個(gè)線段相交的地方稱作結(jié)點(diǎn)，經(jīng)過總結(jié)，共有十字結(jié)點(diǎn)，正T型結(jié)點(diǎn)，左T型結(jié)點(diǎn)，右T型結(jié)點(diǎn)四種結(jié)點(diǎn)，大多數(shù)傳統(tǒng)算法要求對(duì)每一個(gè)結(jié)點(diǎn)進(jìn)行精準(zhǔn)分類再分別處理，而此算法能對(duì)不同類型的結(jié)點(diǎn)進(jìn)行統(tǒng)一處理。

在一個(gè)結(jié)點(diǎn)處，小車正對(duì)且壓在車身下面的那根線我們稱為點(diǎn)a，其正對(duì)著車的左側(cè)的線稱為點(diǎn)b，同理，正對(duì)著車前方的直線稱為點(diǎn)c，右側(cè)稱為點(diǎn)d。

把此節(jié)點(diǎn)稱為點(diǎn)A（見下圖），當(dāng)A為1，稱為無效結(jié)點(diǎn)，A為0，稱為有效節(jié)點(diǎn)，考慮到有多個(gè)結(jié)點(diǎn)，所以A，a，b，c，d用數(shù)組表示，每個(gè)字母的初始值都為0，數(shù)組下標(biāo)最大值為100。再設(shè)定一個(gè)p統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)，初始值為1。此外再設(shè)置一個(gè)調(diào)頭結(jié)點(diǎn)N，N為1則已有調(diào)頭動(dòng)作，否則無。小車去往終點(diǎn)時(shí)途經(jīng)每一個(gè)結(jié)點(diǎn)都計(jì)算一次，在此先介紹我的結(jié)點(diǎn)轉(zhuǎn)向算法。

在遇到結(jié)點(diǎn)時(shí)，若車左轉(zhuǎn)，則：若d[p]為1，則a[p]加1，否則若c[p]為1，則d[p]加1，否則若b[p]為1，則c[p]加1，否則若a[p]為1，則b[p]加1。稱此為左側(cè)結(jié)點(diǎn)轉(zhuǎn)向法。

在遇到結(jié)點(diǎn)時(shí)，若車直走，則：若b[p]為0，則c[p]加1，否則若c[p]為0，則d[p]加1，否則若d[p]為0，則a[p]加1。稱此為前側(cè)結(jié)點(diǎn)轉(zhuǎn)向法。

在遇到結(jié)點(diǎn)時(shí)，計(jì)算方法為：（小車在調(diào)頭動(dòng)作完成后，N置1）當(dāng)小車駛到一個(gè)任意結(jié)點(diǎn)時(shí)，若N為1，則判定此節(jié)點(diǎn)為原結(jié)點(diǎn)，p不變，此時(shí)轉(zhuǎn)向時(shí)再根據(jù)情況同理調(diào)用結(jié)點(diǎn)轉(zhuǎn)向法，此時(shí)p為p，完成轉(zhuǎn)向算法后將N置0。

否則若N為0，若A[p-1]為2，則判定此結(jié)點(diǎn)為已過結(jié)點(diǎn)，p不變此時(shí)轉(zhuǎn)向時(shí)繼續(xù)根據(jù)情況調(diào)用結(jié)點(diǎn)轉(zhuǎn)向法，此時(shí)p為p-1，完成轉(zhuǎn)向算法后將A[p]置為0，為無效結(jié)點(diǎn)。

否則，則立即將a置1，此時(shí)結(jié)點(diǎn)狀態(tài)為新節(jié)點(diǎn)，p加1，A[p]置為1，為有效節(jié)點(diǎn)，此時(shí)若車左側(cè)有線，則調(diào)用左側(cè)結(jié)點(diǎn)轉(zhuǎn)向法，否則調(diào)用前側(cè)結(jié)點(diǎn)轉(zhuǎn)向法，此時(shí)p為p。

以上述算法走到終點(diǎn)時(shí)，已將所走過的每個(gè)結(jié)點(diǎn)都?xì)w納到算法中，每個(gè)小車已走過的結(jié)點(diǎn)都有屬于自己的值，用另一套算法逐個(gè)處理結(jié)點(diǎn)值即可計(jì)算出最短路徑。

在小車回起點(diǎn)時(shí)，我們拋棄原有的一切算法，另起爐灶，此時(shí)要先把所有有效節(jié)點(diǎn)剝離出來，然后按從終點(diǎn)到起點(diǎn)的順序?qū)⒂行Ч?jié)點(diǎn)存到一個(gè)數(shù)組中，在這里先介紹我的第三種算法。

在遇到結(jié)點(diǎn)時(shí)，若此結(jié)點(diǎn)d為1，則左轉(zhuǎn)，否則若c為1，則直走，否則若b為1，則右轉(zhuǎn)，我稱此為結(jié)點(diǎn)回溯法，

由此算法可順利回到起點(diǎn)。因?yàn)樵诿恳粋€(gè)結(jié)點(diǎn)計(jì)算一次，統(tǒng)一計(jì)算再運(yùn)行，故而此算法對(duì)算力要求低，占用運(yùn)行內(nèi)存少，運(yùn)算速度極短，不會(huì)影響其他程序的運(yùn)行。

總結(jié)來說，由結(jié)點(diǎn)轉(zhuǎn)向算法和結(jié)點(diǎn)回溯法即可完美走完迷宮。

但此算法可靈活處理至二級(jí)結(jié)點(diǎn)，對(duì)于處理n級(jí)結(jié)點(diǎn)寫死即可，因此我優(yōu)化了此算法，使其可靈活處理n個(gè)結(jié)點(diǎn)，算法雖簡(jiǎn)單，但寫代碼實(shí)踐時(shí)，其中也有許多細(xì)節(jié)需要處理，但由于篇幅限制，至此不做過多贅述。