c迷宫算法
‘壹’ 迷宫问题，c语言
#include<stdio.h>
int main(void)
{
int maze[100][100];
int MAZE[100][100];
int m,n;
int p,q;
printf("输入迷宫的行数m,列数n:\n");
scanf("%d%d",&m,&n);
for(p=0;p<=n+1;p++){
maze[0][p]=1;
maze[m+1][p]=1;
}
for(p=1;p<=m;p++){
maze[p][0]=1;
maze[p][n+1]=1;
printf("输入第%d行迷宫:\n",p);
for(q=1;q<=n;q++){
scanf("%d",&maze[p][q]);
MAZE[p][q]=maze[p][q];
}
}
struct location{
int row;
int col;
}way[100];
int movehoriz[8]={-1,0,1,1,1,0,-1,-1};
int movevert[8]={1,1,1,0,-1,-1,-1,0};
int endrow=m;
int endcol=n;
way[0].row=1;
way[0].col=1;
int start=3;
int i=0;
int k;
int j;
int found=0;
while(!found){
for(k=start;k<start+8;k++){
if((maze[way[i].row+movevert[k%8]][way[i].col+movehoriz[k%8]]==0)&&((i==0)||((way[i].row!=way[i-1].row)||(way[i].col!=way[i-1].col)))){
way[i+1].row=way[i].row+movevert[k%8];
way[i+1].col=way[i].col+movehoriz[k%8];
i++;
start=(k+5)%8;
break;
}
if((way[i].row==endrow)&&(way[i].col==endcol)){
break;
}
if((maze[way[i].row+movevert[k]][way[i].col+movehoriz[k]]==0)&&(way[i].row==way[i-1].row)&&(way[i].col==way[i-1].col)){
way[i].row=0;
way[i].col=0;
maze[way[i].row][way[i].col]=1;
i--;
start=(start+4)%8;
}
}
if(k>=start+8){
break;
}
if((way[i].row==endrow)||(way[i].col==endcol)){
found=1;
break;
}
}
if(found){
for(j=0;j<=i;j++){
printf("maze[%d][%d]\n",way[j].row,way[j].col);
}
}
else{
printf("The maze does not have a path\n");
}
}
QQ：366597114 不一定完全对。也许有小错误。有问题可以来问我哈
‘贰’ 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;
}
‘叁’ 用C/C++编写迷宫，用A*算法
#include "stdafx.h"
#include <stack>
using namespace std;
//定义常数
const int rows = 8,cols = 8;
//声明全局变量�
HINSTANCE hInst;
HBITMAP ball;
HDC hdc,mdc,bufdc;
HWND hWnd;
DWORD tPre,tNow;
char *str;//记录目前搜索状态的字符串指针
int nowPos,prePos;
bool find;//声明一个布尔变量，以记录是否找到迷宫出口
stack<int> path;//建立一个整型堆栈path
int mapIndex[rows*cols] = { 0,2,0,0,0,0,0,0,
0,1,0,1,1,1,1,0,
0,1,0,1,0,1,1,0,
0,1,0,0,0,1,1,0,
0,1,1,1,1,1,1,0,
0,1,0,0,0,0,1,0,
0,0,1,1,1,1,1,0,
0,0,0,0,0,0,3,0 };
int record[rows*cols];
ATOM MyRegisterClass(HINSTANCE hInstance);
BOOL InitInstance(HINSTANCE, int);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
void MyPaint(HDC hdc);
int APIENTRY WinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPSTR lpCmdLine,
int nCmdShow)
{
MSG msg;
MyRegisterClass(hInstance);
if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}
while( msg.message!=WM_QUIT )
{
if( PeekMessage( &msg, NULL, 0,0 ,PM_REMOVE) )
{
TranslateMessage( &msg );
DispatchMessage( &msg );
}
else
{
tNow = GetTickCount();
if(tNow-tPre >= 100)
MyPaint(hdc);
}
}
return msg.wParam;
}
ATOM MyRegisterClass(HINSTANCE hInstance)
{
WNDCLASSEX wcex;
wcex.cbSize = sizeof(WNDCLASSEX);
wcex.style = CS_HREDRAW | CS_VREDRAW;
wcex.lpfnWndProc = (WNDPROC)WndProc;
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance;
wcex.hIcon = NULL;
wcex.hCursor = NULL;
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName = NULL;
wcex.lpszClassName = "canvas";
wcex.hIconSm = NULL;
return RegisterClassEx(&wcex);
}
//*****************************************
// 1.迷宫拼接地图
// 2.设定小球在迷宫入口处
// 3.按照mapIndex设定record数组的初始内容
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
HBITMAP bmp;
hInst = hInstance;
hWnd = CreateWindow("canvas", "迷宫" , WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
if (!hWnd)
{
return FALSE;
}
MoveWindow(hWnd,10,10,430,450,true);
ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);
hdc = GetDC(hWnd);
mdc = CreateCompatibleDC(hdc);
bufdc = CreateCompatibleDC(hdc);
bmp = CreateCompatibleBitmap(hdc,cols*50,rows*50);
SelectObject(mdc,bmp);
HBITMAP tile;
int rowNum,colNum;
int i,x,y;
//加载位图
tile = (HBITMAP)LoadImage(NULL,"tile.bmp",IMAGE_BITMAP,50,50,LR_LOADFROMFILE);
ball = (HBITMAP)LoadImage(NULL,"ball.bmp",IMAGE_BITMAP,50,50,LR_LOADFROMFILE);
for (i=0;i<rows*cols;i++)
{
record[i] = mapIndex[i];
rowNum = i / cols; //求列编号
colNum = i % cols; //求行编号
x = colNum * 50; //求贴图X坐标
y = rowNum * 50; //求贴图Y坐标
SelectObject(bufdc,tile);
if(!mapIndex[i]) //如果是0，就贴墙
BitBlt(mdc,x,y,50,50,bufdc,0,0,SRCCOPY);
else //通道
{
if(mapIndex[i] == 2) //找到迷宫出口
{
nowPos = i;
path.push(i);
record[i] = 0;
}
BitBlt(mdc,x,y,50,50,bufdc,0,0,WHITENESS);//WHITENESS 白色50*50的方块
}
}
prePos = cols * rows + 1;
MyPaint(hdc);
return TRUE;
}
//*************************************
// 搜寻可行走路径及小球移动贴图
void MyPaint(HDC hdc)
{
int rowNum,colNum;
int x,y;
int up,down,left,right;
//清除上次贴图
rowNum = prePos / cols;
colNum = prePos % cols;
x = colNum * 50;
y = rowNum * 50;
SelectObject(bufdc,ball);
BitBlt(mdc,x,y,50,50,bufdc,0,0, WHITENESS);
//贴小球
rowNum = nowPos / cols;
colNum = nowPos % cols;
x = colNum * 50;
y = rowNum * 50;
SelectObject(bufdc,ball);
BitBlt(mdc,x,y,50,50,bufdc,0,0, SRCCOPY);
if(!find)
{
str = "搜寻出口中...";
up = nowPos - cols;
down = nowPos + cols;
left = nowPos - 1;
right = nowPos + 1;
if(up>=0 && record[up]) //往上走�
{
path.push(up);
record[up] = 0;
prePos = nowPos;
nowPos = up;
if(mapIndex[nowPos] == 3) //找到出口
find = true;
}
else if(down<=cols*rows-1 && record[down]) //下
{
path.push(down);
record[down] = 0;
prePos = nowPos;
nowPos = down;
if(mapIndex[nowPos] == 3)
find = true;
}
else if(left>=rowNum*cols && record[left]) //左
{
path.push(left);
record[left] = 0;
prePos = nowPos;
nowPos = left;
if(mapIndex[nowPos] == 3)
find = true;
}
else if(right<=(rowNum+1)*cols-1 && record[right]) //右
{
path.push(right);
record[right] = 0;
prePos = nowPos;
nowPos = right;
if(mapIndex[nowPos] == 3)
find = true;
}
else //无�
{
if(path.size() <= 1) //回到入口����
str = "迷宫没有出口...";
else
{
path.pop();
prePos = nowPos;
nowPos = path.top();
}
}
}
else
{
str = "找到出口了!";
}
TextOut(mdc,0,0,str,strlen(str));
BitBlt(hdc,10,10,cols*50,rows*50,mdc,0,0,SRCCOPY);
tPre = GetTickCount();
}
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
switch (message)
{
case WM_KEYDOWN:
if(wParam==VK_ESCAPE)
PostQuitMessage(0);
break;
case WM_DESTROY:
DeleteDC(mdc);
DeleteDC(bufdc);
DeleteObject(ball);
ReleaseDC(hWnd,hdc);
PostQuitMessage(0);
break;
default:
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}
‘肆’ C语言迷宫问题，求该算法的时间和空间的复杂度。迷宫的路径已经定义好，求出路的算法。
该算法是不稳定的，其时空复杂度不仅和m,n有关，还和mg[][]的具体数值有关。
最坏情况下：每个点都试探过才走到终点。此时时间复杂度为：(m*n-1)*4，（其中4为4个方向），空间复杂度m*n*2，(其中m*n为存储迷宫图空间，m*n为栈空间);
再好情况下：一次试探过就走到终点。此时时间复杂度为：(min(m,n)-1)，空间复杂度m*n;
所以：
该算法时间复杂度为：[(m*n-1)*4+(min(m,n)-1)]/2，约为2×m×n
空间复杂度为3*m*n/2
‘伍’ 求解c语言一递归迷宫问题
给你给伪算法：（设坐标为x,y,坐标向右和下延生。）
函数：
｛
判断当前是不是（7,7)，如果是，表示走出迷宫。打印轨迹
1 尝试往左先走一步（x-1，如果x小于0，或者对应位置标识为阻塞）
2 1如果成功，用本函数递归调用左走一步的坐标，并记下当前位置到轨迹列表。
3 尝试往前先走一步（y+1，如果y小于0，或者对应位置标识为阻塞）
4 3如果成功，用本函数递归调用前走一步的坐标,并记下当前位置到轨迹列表。
5 尝试往右先走一步（x+1，如果x小于0，或者对应位置标识为阻塞）
6 5如果成功，用本函数递归调用前走一步的坐标,并记下当前位置到轨迹列表。
如果是（0，0），表示没有合适的路径可走出迷宫。
如果不是（0，0），将轨迹列表最后一位弹出。
｝
‘陆’ c语言，用二维数组解决迷宫问题。来段完整的代码吧。
好的，以下是使用二维数组解决迷宫问题的C语言代码示例：
Copy code
#include <stdio.h>
#define ROW 6 // 迷宫行数
#define COL 6 // 迷宫列数
int maze[ROW][COL] = { // 迷宫地图 1表兄银碰示障碍，0表示通路
{1, 1, 1, 1, 1, 1},
{1, 0, 0, 1, 0, 1},
{1, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 0, 1},
{1, 1, 1, 1, 1, 1},
};
int result[ROW][COL]; // 存放走迷宫的结果
int dfs(int row, int col) {
if (row == ROW - 1 && col == COL - 1) { // 到达终点
result[row][col] = 1;
return 1;
}
if (maze[row][col] == 0) { // 当前位置是通路
result[row][col] = 1;
if (row < ROW - 1 && dfs(row + 1, col)) { // 向下走有解
return 1;
}
if (col < COL - 1 && dfs(row, col + 1)) { // 向右走有解
return 1;
}
result[row][col] = 0; // 标记走过的路
}
return 0; // 返回无解羡谈
}
void print_result() {
printf("走迷宫的结果：\n");
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
printf("%d ", result[i][j]);
}
printf("\n");
}
}
int main() {
if (dfs(0, 0)) { // 从起点开始走迷宫
print_result();
} else {
printf("无法走出迷宫！\n");
}
return 0;
}
上述搏碰代码中，我们使用了一个二维数组 maze 来表示迷宫地图，其中 1 表示障碍，0 表示通路；另一个二维数组 result 用来存储走迷宫的结果，其中 1 表示该位置走通了， 0 表示该位置没有走通。
我们使用 dfs 函数来进行深度优先搜索，从起点 (0, 0) 开始往下、往右走，直到走到终点 (ROW-1, COL-1)，如果存在通路，则将路径标记在 result 数组中，并返回 1，否则返回 0 表示无解。
最后，我们在 main 函数中调用 dfs 函数，判断是否能从起点走出迷宫，如果有解，则输出走迷宫的结果；否则，输出 "无法走出迷宫" 的提示。