題目
思路和解題方法
問題理解：此題要求找出將一條由16節正方形構成的玩具蛇放入4x4的方格中的不同方式數。每節蛇可以是直線或直角轉彎，且蛇的形狀需要完全覆蓋盒子里的16個格子，每個格子僅被蛇的一個部分占據。
狀態表示：使用一個二維數組
st[4][4]來標記每個格子是否被蛇占用（0表示未占用，1表示占用）。同時，使用深度優先搜索（DFS）來探索所有可能的放置方式。DFS策略：
- 參數定義：
dfs(x, y, len)函數中，x和y表示當前蛇頭的位置坐標，len表示當前已經放置蛇的節段數目。- 遞歸終止條件：當
len達到16時，說明蛇的所有部分都已放置完畢，方案數加1。- 邊界判斷與重復檢查：每次嘗試移動前，先檢查新位置是否在邊界內以及是否已訪問過。
- 移動方向：對于當前位置，嘗試向上、下、左、右四個方向移動，每次移動后遞歸調用自身，探索新的路徑。
- 回溯：在每個方向探索結束后，需要恢復現場，即撤銷當前位置的占用標記，以允許探索其他路徑。
代碼實現：
- 首先遍歷所有可能的起始位置，對每個起始位置調用
dfs函數。- 在
dfs函數中，進行上述邏輯處理，包括移動、計數、回溯等操作。
c++ 代碼
#include <iostream>
using namespace std;// 方向數組，dx表示行變化，dy表示列變化，分別對應上、下、左、右四個方向
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};// st數組用來標記網格中的每個格子是否已經被蛇占用過
int st[4][4]; // res用于記錄可以成功放置玩具蛇的總方案數
int res = 0; // 深度優先搜索函數，探索放置蛇的路徑
void dfs(int x, int y, int len) {// 如果當前位置超出網格范圍，則返回if (x < 0 || y < 0 || x >= 4 || y >= 4) {return; }// 如果當前位置已經走過，則返回，避免重復路徑if (st[x][y] == 1) {return; }// 如果蛇的長度已經達到15（即全部擺放完畢），方案數加一并返回if (len == 15) {res++; return;}// 標記當前位置已被占用st[x][y] = 1; // 依次嘗試向上、下、左、右四個方向進行下一步探索for (int i = 0; i < 4; i++) {dfs(x + dx[i], y + dy[i], len + 1); }// 回溯：恢復當前位置為未訪問狀態，以便進行其他路徑的探索st[x][y] = 0;
}// 主函數
int main() {// 遍歷網格的每一個起點，啟動深度優先搜索尋找所有可能的蛇形路徑for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {dfs(i, j, 0);}}// 輸出所有可行的蛇形路徑總數cout << res << endl; return 0;
}Java 版本（僅供參考）
import java.util.Arrays;public class Main {static int[][] st = new int[4][4]; static int res = 0; static int[][] dx_dy = {{-1, 0, 1, 0}, {0, -1, 0, 1}}; public static void dfs(int x, int y, int len) {if (x < 0 || y < 0 || x >= 4 || y >= 4) {return; }if (st[x][y] == 1) {return; }if (len == 15) {res++; return;}st[x][y] = 1; for (int i = 0; i < 4; i++) {dfs(x + dx_dy[0][i], y + dx_dy[1][i], len + 1); }st[x][y] = 0; }public static void main(String[] args) {Arrays.stream(st).forEach(row -> Arrays.fill(row, 0)); // 初始化st數組for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {dfs(i, j, 0);}}System.out.println(res); }
}Python 版本（僅供參考）
def dfs(x, y, len):if x < 0 or y < 0 or x >= 4 or y >= 4:returnif st[x][y] == 1:returnif len == 15:global resres += 1returnst[x][y] = 1for i in range(4):dfs(x + dx[i], y + dy[i], len + 1)st[x][y] = 0dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
st = [[0]*4 for _ in range(4)]
res = 0for i in range(4):for j in range(4):dfs(i, j, 0)print(res)代碼細節：
- 遞歸函數：
dfs(x, y, len)負責實際的搜索過程，其中(x, y)是當前探索的位置，len表示已經探索了多少個格子（即蛇的長度）。 - 邊界檢查：在嘗試移動到新位置之前，先檢查新位置是否還在網格范圍內，防止越界。
- 重復檢查：通過
st數組避免重復訪問同一格子，提高搜索效率，減少無效分支。 - 遞歸終止條件：當蛇的長度達到16時，說明找到了一個完整的解決方案，累加結果計數器
res。 - 回溯：在遞歸返回前，撤銷當前位置的占用標記，以便于從當前節點出發探索其他路徑。
- 全面搜索：通過外層循環遍歷所有可能的起始點，確保從每個格子出發都嘗試尋找解。
覺得有用的話可以點點贊，支持一下。
如果愿意的話關注一下。會對你有更多的幫助。
每天都會不定時更新哦? >人<? 。
