數字迷宮c語言
『壹』 c語言數字迷宮問題怎麼做圖片如下
可以參考八皇後問題用回溯的方式來解決。
這道迷宮題，觀察一下，與某個格子相鄰的格子至多為4個，也就是有4種可能的前進方向，需要窮舉所有可能。在窮舉下一種可能前，需要恢復初始狀態（即回溯）。寫了一個簡單的代碼，還有很多需要優化的地方，但關鍵是能用^_^，你可以調試一下，把實現的思路寫出來，就可以順利完成這道題了。
#include <stdio.h>
#include <string.h>
/***
1、 迷宮大小n*n，擴展為(n+2)*(n+2)，外圍一圈的格子作為不可再前進的邊界。
2、 若所有相鄰格子均已訪問，表明此路不通，回溯。
3、 計數器達到總步數，檢查是否位於終點及中間路徑是否合法，通過則顯示。
4、 查找函數Lookup()以遞歸方式反復調用自身，a->b->c->...，以查找某條可能的路徑。
...c,b,a等返回前，均回溯，逐步恢復tag。
離開a時，tag已經恢復到初始狀態，如此就不影響查找其他路徑了。
5、 若迷宮夠大或數據特別，都可能存在不同的路線
6、 先查看main()，了解基本步驟及初始化過程
***/
const int N = 6;
// eg1. N = 6
int row[N] = { 0, 4, 3, 1, 3, 0}; // 4 + 3 + 1 + 3 = 11
int col[N] = { 0, 1, 4, 3, 3, 0};
// eg2. N = 6
//int row[N] = { 0, 3, 4, 4, 2, 0}; // 3 + 4 + 4 + 2 = 13
//int col[N] = { 0, 3, 2, 4, 4, 0};
// eg3. N = 8
//int row[N] = { 0, 3, 1, 4, 3, 3, 1, 0};
//int col[N] = { 0, 1, 1, 5, 3, 1, 4, 0};
// 計數器
// Lookup()用g_counter與COUNTER比較是否走到了規定的步數
int g_counter = 0; // 無論是否成功，每查找一條路徑後自動恢復為0
int COUNTER = 0; // 總步數，等於row（或col）數組各元素之和，在main()中初始化
// Lookup()用tag記錄行走狀況
// 在main()中初始化
// 每查找一條路徑後自動恢復為初始狀態
struct _tag
{
int row[N];
int col[N];
int arr[N][N]; // 走過，按順序標記
} tag;
// 顯示迷宮
// inside為false時，列印擴展的迷宮
// inside為true時，列印未擴展的迷宮
void Display(bool inside)
{
int i, j;
for (i = 0; i < N; i++)
{
if ((i == 0 || i == N-1) && inside)
continue;
for (j = 0; j < N; j++)
{
if ((j == 0 || j == N-1) && inside)
printf("%4s", " ");
else
printf("%4d", tag.arr[i][j]);
}
printf(" ");
}
printf(" ");
}
// 檢查路徑是否符合已給條件
bool Check()
{
bool b = true;
int sum_row, sum_col;
for (int i = 1; i < N-1; i++)
{
sum_row = 0;
sum_col = 0;
for (int j = 1; j < N-1; j++)
{
sum_row += tag.arr[i][j] > 0 ? 1 : 0;
sum_col += tag.arr[j][i] > 0 ? 1 : 0;
}
if (sum_row != row[i] || sum_col != col[i])
{
b = false;
break;
}
}
return b;
}
// 遞歸查找路徑，返回前擦除痕跡，恢復現場
// 當前訪問的格子(i,j)，i:行坐標，j:列坐標
void Lookup(int i, int j)
{
g_counter++; // 總步數加1
tag.arr[i][j] = g_counter; // visited
tag.row[i]--; // 行計數減1
tag.col[j]--; // 列計數減1
// 走完了
if (g_counter >= COUNTER)
{
// 位於終點，且路徑合法
if (i == N-2 && j == N-2 && Check())
{
Display(true);
}
// 此格子已判別，恢復現場，以查找其他路徑（此即回溯的思想）
tag.arr[i][j] = 0;
tag.row[i]++;
tag.col[j]++;
g_counter--;
return;
}
// 行方向
if (tag.row[i] > 0)
{
if (!tag.arr[i][j+1])
{
Lookup(i, j+1); // 從當前格子向右走一步
}
if (!tag.arr[i][j-1])
{
Lookup(i, j-1); // 從當前格子向左走一步
}
}
// 列方向
if (tag.col[j] > 0)
{
if (!tag.arr[i+1][j])
{
Lookup(i+1, j); // 從當前格子向下走一步
}
if (!tag.arr[i-1][j])
{
Lookup(i-1, j); // 從當前格子向上走一步
}
}
// 此格子已判別，恢復現場，以查找其他路徑（此即回溯的思想）
tag.arr[i][j] = 0;
tag.row[i]++;
tag.col[j]++;
g_counter--;
}
int main()
{
// 格子初始化為全0
memset(tag.arr, 0, sizeof(tag.arr));
for (int i = 0; i < N; i++)
{
tag.row[i] = row[i];
tag.col[i] = col[i];
COUNTER += row[i];
tag.arr[0][i] = 1;
tag.arr[N-1][i] = 1;
tag.arr[i][0] = 1;
tag.arr[i][N-1] = 1;
}
printf("初始化: ");
Display(false);
printf("合法路徑: ");
Lookup(1, 1); // 從格子(1, 1)出發
//getchar();
return 0;
}