藍橋杯“數字接龍”賽題算法研究和實現

摘要：隨著信息化建設的不斷深入，計算機專業對學生掌握計算機基礎語言及基本數據結構的要求越來越高，為了更好地幫助學生和教師了解當前大學生程序設計競賽的命題方向和重點，該文深入分析了2024年藍橋杯比賽賽題“數字接龍”，采用深度優先搜索算法，提供了C++語言的遞歸和非遞歸實現，并通過構造相關用例測試遞歸和非遞歸實現，結果一致，為學生和教師掌握深度優先遍歷算法解決迷宮問題提供了重要的參考和思路。

關鍵詞：棧；隊列；遞歸；搜索算法；藍橋杯

中圖分類號：TP311" " " 文獻標識碼：A

文章編號：1009-3044（2025）12-0001-06

開放科學（資源服務） 標識碼（OSID）

0 引言

計算機是一門實踐性很強的學科，除了掌握編程語言的基本語法外，分析問題的能力、靈活運用數據結構的能力、設計算法的能力也是能夠應對未來挑戰的必備能力[1]。藍橋杯大賽由工業和信息化部人才交流中心主辦，國信藍橋教育科技（北京） 股份有限公司承辦，是高校教育教學改革和創新人才培養的重要競賽項目[2]，對推動我國軟件和信息技術產業的發展以及促進軟件和信息化技術人才的培養起到了積極作用[3]。

本文對2024年賽題“數字接龍”問題進行分析，采用深度優先搜索算法，提供了C++語言的遞歸和非遞歸兩種實現方式，為學生和教師掌握深度優先遍歷算法解決迷宮問題提供了重要的參考和思路。

1 問題分析

1.1 問題描述

【題目描述】小藍最近迷上了一款名為《數字接龍》的迷宮游戲，游戲在一個大小為N × N 的格子棋盤上展開，其中每一個格子處都有著一個 0～K - 1 的整數。游戲規則如下：

（1） 從左上角 （0， 0） 處出發，目標是到達右下角 （N - 1， N - 1） 處的格子，每一步可以選擇沿著水平/垂直/對角線方向移動到下一個格子。

（2） 對于路徑經過的棋盤格子數字序列需滿足：0， 1， 2，...， K - 1， 0， 1， 2，...， K - 1， 0， 1， 2 ...

（3） 途中需要對棋盤上的每個格子恰好都經過一次（僅一次） 。

（4） 路徑中不可以出現交叉的線路。例如之前有從 （0， 0） 移動到 （1， 1），那么再從 （1，0） 移動到 （0，1） 線路就會交叉。

為了方便表示，我們對可以行進的所有八個方向進行了數字編號，如圖2 所示；因此行進路徑可以用一個包含 0～7 的數字字符串表示，如圖 1是一個迷宮示例，它所對應的答案就是：41255214。

1.2 問題分析

本題題意不難理解，典型的迷宮問題。迷宮問題通常使用圖的搜索算法，包括深度優先搜索（DFS） 和廣度優先搜索（BFS） ，其中DFS包含了遞歸和非遞歸兩種實現，DFS非遞歸實現借助于棧，通常用于枚舉搜索路徑，BFS借助于隊列，通常用于解決最短路徑的問題[4-5]。因此，本題應采用 DFS 算法。針對本題有以下分析：

（1） 迷宮的起點（0，0），迷宮的終點（N-1，N-1），按圖3建立坐標系，使用二維數組存儲每個節點的值。輸入的數據可用二維數組表示其權值，如a[3][3]={{0，2，0}， {1，1，1}， {2，0，2}}。

（2） 任意節點（x，y）其相鄰的節點包含8個方向，對應的坐標如表1所示。方向0為（x-1，y），方向1為（x-1，y+1），方向2為（x，y+1），方向3為（x+1，y+1），方向4為（x+1，y），方向5為（x+1，y-1），方向6為（x，y-1），方向7為（x-1，y-1）。

（3） 題目要求輸出字典序最小的路徑，即8個方向規定了先后順序。可借助一個二維數組或者兩個一維數組來規定方向及其順序，如定義int directory[][2]=

{{-1，0}， {-1，1}， {0，1}， {1，1}， {1，0}，{ 1，-1}， {0，-1}， {-1，-1}}，某節點（x，y）的相鄰節點可通過遍歷directory數組獲得，假設遍歷時的循環變量為i，則某節點（x，y）相鄰節點即（x+directory[i][0]，y+directory[i][1]），其中i則表示方向，從0至7。

（4） 每個格子恰好經過一次。使用二維數組表示每個節點是否被訪問過，如visit[x][y]= 0表示未訪問過，visit[x][y]=1表示已訪問過。搜索成功時要求數組元素全為1。

（5） 不允許路徑交叉。對于任意的節點（x，y），其相鄰節點路徑存在交叉有4種情況，如圖4所示，圖中實線箭頭表示點（x，y）下一步的方向，虛線箭頭表示已經訪問過的點訪問時的方向，圖4的描述如表2所示。

由表2可知，偶數方向不會交叉，每個點的下一步方向值需保存，判斷是否交叉時需使用，奇數方向是否交叉取決于下一步方向值的前后方向（方向1的前后方向為0和2，方向3的前后方向為2和4，方向5的前后方向為4和6，方向7的前后方向為6和0） 上的點是否都被訪問并且訪問時的方向為當前點的下一步方向值+2或-2（由于方向值范圍為0到7，為了避免負數，-2等價于+6，為了避免超過7，可對8取模） 。

（6） 對于尋找終點的過程為一棵搜索樹，該搜索樹如圖5所示。設f（x，y）表示從（x，y）點到終點是否存在有效路徑，則f（x，y）為0表示不存在有效路徑，f（x，y）為1表示存在有效路徑。本問題轉化為尋找（x，y）的相鄰點即（x-1，y）（x-1，y+1）...8個方向的點到終點的有效路徑，進而進一步搜索，直到（x，y）為終點為止。

由此可得，本題在迷宮問題的基礎上添加了固定方向、節點都被訪問、路徑不允許交叉等條件，使迷宮變得更為復雜。分析圖5的搜索樹可知：

（1） 由于迷宮節點要求全覆蓋，則搜索樹的高度為n×n-1，例如本題的3×3的矩陣，9個點就會產生8個方向，由于n≤10，因此高度h≤99。

（2） 每個節點的子節點數量≤8。第i層節點個數≤8i-1?？偣濣c個數≤（8h-1）/7≤（899-1）/7。

（3） 搜索過程中的節點（x，y）如果下標越界，則節點無效，即x和y需滿足在[0，n）范圍內。

（4） 搜索過程節點的權值a[x][y]要滿足其相鄰節點權值等于（a[x][y]+1）%k，即a[x+directory[i][0]][y+directory[i]

[1]]=（a[x][y]+1）%k。

（5） 每個節點搜索過后需標記為1，即visit[x][y]=1。搜索過的節點不再有效，即visit[x][y]=0的節點才是有效節點，可訪問。

（6） 路徑無交叉，則某節點（x，y）的在i方向上（i為奇數） 的相鄰節點為（x+directory[i][0]，y+directory[i][1]），i方向的前一個方向的點坐標為（x+directory[i-1][0]，y+directory[i-1][1]），i方向的后一個方向的點坐標為（x+directory[i+1][0]，y+directory[i+1][1]），若兩個節點都被訪問且訪問時的方向滿足前者下一步方向值為i+2或后者下一步方向值為i+6。因此，借助二維數組nextDir[x][y]記錄每個點的下一步方向值，初始化時均為-1。為避免i+1或下一步方向值超過7，可使用模運算，如果下標超過范圍，則無須判斷，不會交叉。

（7） 找到終點時存在以下兩種情況：

① 所有節點均被訪問，則輸出結果路徑，程序結束。

② 存在節點未被訪問，回溯到上一步繼續搜索。

（8） 找到終點時，需要將路徑輸出，即按照nextDir[x][y]輸出即可。

另外，廣度優先搜索BFS算法通常用于求解最短路徑問題，若用來求解本題，則需要記錄每個節點搜索過程中來時的路徑，每個節點可能需要開辟額外的n×n的數組，由于搜索層高可達99，耗費的空間呈指數增長，效率太低。

2 算法實現

2.1 DFS遞歸實現

根據1.2小節的分析，本題可通過遞歸來實現，遞歸包含兩個要素：邊界條件和遞歸通式。即：

（1） 遞歸通式：f（x，y）=f（x-1，y）||f（x-1，y+1）||...（8個方向有一個能找到終點則返回1） ，其中

[f（x，y）=1，存在有效路徑" " "0，不存在有效路徑]

（2） 邊界條件：（x，y）為終點且所有節點被訪問。

遞歸實現DFS時，需要定義以下常量、變量以及函數：

int directoryLength=8;

int directory[][2]=

{{-1，0}，{-1，1}，{0，1}，{1，1}，{1，0}，{1，-1}，{0，-1}，{-1，-1}};

const int N=10;

int n，k;

int a[N][N];//存放權值，即輸入

int visit[N][N];//標記是否已訪問，初始化時僅visit[0][0]=1其他均為0

int nextDir[N][N];//記錄下一步的方向值，初始化時均為-1

//1. 判斷節點是否有效

int valid（int x，int y）{

return xgt;=0amp;amp;xlt;namp;amp;ygt;=0amp;amp;ylt;n;}

//2. （x，y）相鄰節點是否交叉，不交叉返回0

int cross（int x，int y，int i）{

if（i%2==0）

return 0;

int frontX=x+directory[i-1][0];

//前一個方向

int frontY=y+directory[i-1][1];

int backX=x+directory[（i+1）%

directoryLength][0];//后一個方向

int backY=y+directory[（i+1）

%directoryLength][1];

if（！valid（frontX，frontY）||！valid（backX，backY））//節點無效不交叉

return 0;

return visit[frontX][frontY]amp;amp;visit[backX][backY]amp;amp;（nextDir[frontX][frontY]==（i+2）%directoryLength||nextDir[backX][backY]==（i+6）%directoryLength）; }

//3. 輸出結果。結果存在nextDir矩陣中，輸出即可。

void printResult（）{

int x=0，y=0;

while（?。▁==n-1amp;amp;y==n-1））{

int dir=nextDir[x][y];

coutlt;lt;dir;

x=x+directory[dir][0];

y=y+directory[dir][1];}

}

//4. 判斷是否所有節點都被訪問，都被訪問返回1，否則返回0

int allVisit（）{

int i，j;

for（i=0;ilt;n;i++）

for（j=0;jlt;n;j++）

if（visit[i][j]==0）

return 0;

return 1;

}

//5. 初始化訪問矩陣visit和下一步方向值矩陣nextDir

void init（）{

int i，j;

for（i=0;ilt;n;i++）

for（j=0;jlt;n;j++） {

visit[i][j]=0;

nextDir[i][j]=-1; }

}

DFS遞歸實現流程圖如圖6所示。流程描述如下：

步驟1：定義遞歸函數，參數為節點坐標x和y；

步驟2：判斷該坐標是否為終點，如果是終點，則判斷是否所有節點都被訪問：

① 是，則輸出結果返回成功1。

② 否，則返回0，退出當前函數調用繼續查找。

步驟3：判斷該坐標是否為終點，如果不是終點，則按8個方向循環遍歷所有相鄰節點；

步驟4：相鄰節點無效，則繼續遍歷下一個相鄰節點；

步驟5：若相鄰節點有效（節點坐標有效，符合順序要求，未交叉） 且未被訪問，則標記該相鄰節點已訪問，修改下一步方向值矩陣，遞歸調用函數查找下一個節點是否存在到終點的路徑，如果存在則返回查找成功1，否則回溯到遞歸調用前的狀態，即把該相鄰節點標記未訪問，下一步方向值矩陣復原；

步驟6：若所有相鄰節點都訪問完均未找到從起點到終點的有效路徑，則查找失敗返回0。

按照圖6，C++代碼實現如下：

int dfs（int x，int y）{

if（x==n-1amp;amp;y==n-1）//到達終點

if（allVisit（））{//所有節點都訪問，則搜索成功，輸出結果并返回

printResult（）;

return 1;

}else

return 0; //搜索失敗

for（int i=0;ilt;directoryLength;i++）{

int nextX=x+directory[i][0];

int nextY=y+directory[i][1];" " if（valid（nextX，nextY）amp;amp;（a[nextX][nextY]==（a[x][y]+1）%k）

amp;amp;！cross（x，y，i）amp;amp;visit[nextX][nextY]！=1{

visit[nextX][nextY]=1;

//標記相鄰節點已訪問

nextDir[x][y]=i;

if（dfs（nextX，nextY））

//找到結果則返回

return 1;

visit[nextX][nextY]=0;

//未找到結果則回溯

nextDir[x][y]=-1;

}

}

return 0;

}

int main（）{

cingt;gt;ngt;gt;k;

int i，j;

for（i=0;ilt;n;i++）

for（j=0;jlt;n;j++）

cingt;gt;a[i][j];

init（）;//初始化矩陣

visit[0][0]=1;//標記起點已訪問

if（n==1）//邊界情況

coutlt;lt;-1;

if（！dfs（0，0））

coutlt;lt;-1;

}

2.2 DFS非遞歸實現

DFS 也可以采用非遞歸實現，非遞歸實現時需要借助棧，在C++中可以使用vector或stack。本題的每個節點需記錄坐標x，y，下一步的方向值仍使用矩陣，初始化時，起點為（0，0），所有點的下一步方向值均為-1，借助類或者結構體或者數組定義節點信息，如：

class Node{

public：

int x;

int y;

Node（int x， int y） {

this-gt;x = x;

this-gt;y = y;

}

};

或

struct Node{

int x;

int y;

};

非遞歸實現時對節點進行入棧和出棧操作，因此定義棧stacklt;Nodegt; st，判斷節點是否有效、相鄰節點是否交叉、節點是否都被訪問、輸出結果等函數同遞歸實現。非遞歸實現依賴于棧的先進后出特性，通過入棧和出棧操作來保存搜索過程。搜索過程流程如圖7所示。流程描述如下：

步驟1：起點初始化時nextDir均設置為-1，將起點入棧；

步驟2：判斷棧是否為空，若為空，則結束；

步驟3：若棧不為空，獲取棧頂元素賦值給cur，判斷cur是否為有效的終點，即是終點且所有節點都被訪問，如果是，則輸出結果返回；

步驟4：如果cur不是有效終點，則獲取cur的下一步方向值d，執行d++；

步驟5：遍歷從d開始的方向，判斷該方向值是否超過7，超過7則說明所有相鄰節點都不存在到終點的有效路徑，則當前節點無效，將cur出棧，并且cur標記為未訪問，執行步驟2，從cur的上一個節點的下一個方向開始重新查找；

步驟6：方向值不超過7，則修改棧頂cur的d為當前處理的方向，判斷該方向上的相鄰節點是否有效（節點坐標有效，符合順序要求，未交叉） 且未訪問，如果是，則標記當前節點已訪問，該相鄰節點入棧，回到步驟2執行；

步驟7：如果該方向上的相鄰節點不滿足有效且未訪問，則重新獲取cur的方向d，回到步驟4執行。

按照圖7，C++代碼如下：

cingt;gt;ngt;gt;k;

int i，j;

for（i=0;ilt;n;i++）

for（j=0;jlt;n;j++）

cingt;gt;a[i][j];

init（）;//初始化矩陣

if（n==1）{ //邊界

coutlt;lt;-1;

return 0;

}

Node start（0，0）;

st.push（start）;//起點入棧

visit[0][0]=1; //標記起點已訪問

while （！st.empty（）） {

Node node=st.top（）;//獲取棧頂

int x=node.x;

int y=node.y;

int d=nextDir[x][y];

if（x==n-1amp;amp;y==n-1amp;amp;allVisit（））{

//如果棧頂為終點并且所有節點被訪問

printResult（）; //輸出結果返回

return 1;

}

d++; //獲取棧頂節點的方向

int flag=0;

for（i=d;ilt;directoryLength;i++）{ //從當前方向開始循環遍歷后續所有方向的結點

int nextX=x+directory[i][0];//獲取i方向上的節點坐標

int nextY=y+directory[i][1];

nextDir[x][y]=i;//設置當前棧頂節點的方向值為i if（valid（nextX，nextY）amp;amp;（a[nextX][nextY]==（a[x][y]+1）%k）amp;amp;

！cross（x，y，i）amp;amp;visit[nextX][nextY]！=1）{//如果該方向節點有效

Node next（nextX，nextY）;

st.push（next）;//該方向的下一個節點入棧

visit[nextX][nextY]=1;

flag=1; //標記找到符合條件的下一個節點

break;

}

}

if（！flag）{//如果沒有找到符合條件的下一步節點則回溯

visit[x][y]=0;

st.pop（）;

nextDir[x][y]=-1;

}

} coutlt;lt;-1lt;lt;endl;

3 測試用例

DFS的遞歸和非遞歸實現均能通過給定的樣例，運行結果如圖8所示。此外，本題約束N的范圍從1開始，因此需要考慮N=1的特殊情況，當N=1時只有一個節點，不存在任何方向行進，因此需輸出-1，實現時需要考慮邊界做邊界的特殊處理。

測試以下用例，遞歸和非遞歸執行結果如表3所示。兩者執行結果保持一致。驗證了算法實現的正確性。

遞歸和非遞歸均可實現DFS搜索算法，其中非遞歸需要借助于棧，對考生的要求更高，考生需具備一定的數據結構基礎，并且對數據結構的操作函數比較熟悉。

4 總結

本文分析了藍橋杯的“數字接龍”賽題，在迷宮問題的基礎上增加了固定方向、所有節點均需訪問、路徑不允許交叉等條件，使迷宮問題變得更為復雜，本文采用深度優先搜索算法，提供了C++語言的遞歸和非遞歸兩種實現方式，為學生和教師掌握深度優先遍歷算法解決迷宮問題提供了重要的參考和思路。

參考文獻：

[1] 邱維陽.藍橋杯賽題“填充” 的貪心與動態規劃算法分析[J].電腦知識與技術，2024，20（10）：156-158.

[2] 龔春亞，喻子劍.藍橋杯“奇怪的比賽” 賽題遞歸與非遞歸解題算法的研究[J].電腦知識與技術，2021，17（17）：215-216，221.

[3] 陳雨龍，許新華，錢詩佳.“藍橋杯” 軟件類國賽基本數據分析與建議[J].現代信息科技，2021（6）：119-122.

[4] 嚴蔚敏，李冬梅，吳偉民.數據結構：C語言版[M].2版.北京：人民郵電出版社，2015：54-83，160-165.

[5] 羅勇軍，楊培林.程序設計競賽專題挑戰教程[M].北京：人民郵電出版社，2023.

【通聯編輯：王 力】