数字迷宫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;
}