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 函數，判斷是否能從起點走出迷宮，如果有解，則輸出走迷宮的結果；否則，輸出 "無法走出迷宮" 的提示。