基于深度及广度优先搜索的迷宫问题的演示-白红宇

基于深度及广度优先搜索的迷宫问题的演示

阅读量：5048 次

发布时间：2019-06-12

本文共 8932 字，大约阅读时间需要 29 分钟。

1 时间复杂度分析

由于该图采用邻接矩阵存储，整个算法遍历的过程所花费的时间复杂度为该矩阵的N(row*col)。而由于其需要分别访问已经定位，需要进行分别2次操作，如下：

visited = new bool[col*row];//访问标记for (i=0; i

因此在遍历的时候所需要的时间复杂度为N（2*row*col）。

由于深度优先搜索和广度优先搜索都是采用同样的存储方式，并且都是遍历搜索，因此时间复杂度相同，都是N（2*row*col）。

（注：row,col分别表示迷宫的行和列）。

2 空间复杂度分析

5.2.1 深度优先搜索空间复杂度分析

当进行深度优先搜索时，所遍历的最短路径即为单一路径，因此最好的空间复杂度是N（row+col），而最坏情况为N（row*col），即通过了最大的回溯之后才找到终点路径。

5.2.2广度优先搜索空间复杂度分析

当进行广度优先搜索的时候，路径经过所有可能的路径，即最大为row*col，因此，空间复杂度为N（row*col）。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            const int CELL = 25;// 单元像素宽const int W = 15; // 迷宫宽度const int H = 15; // 迷宫高度struct POSITION//每一个单元格的左上坐标{ int x;//单元格横坐标(单位pixel) int y;//单元格纵坐标 int index_x;//单元格横标 int index_y;//单元格纵标};struct MazeEdge//储存的是原来迷宫所拆的墙，下次生成迷宫和原来一样拆{ int x; int y; int z; int w;};struct Wall{ int wall_r;//右墙数据 int wall_l;//左墙数据 int wall_t;//上墙数据 int wall_b;//下墙数据};LRESULT CALLBACK WndProc ( HWND, UINT, WPARAM, LPARAM);//窗口函数void DrawWhiteGround (HDC hdc);//将整个客户区绘制为白色void DrawRedBlock (HDC hdc, int l, int t, int r, int b);//绘制迷宫起始点与终止点void DrawRect (HDC hdc, int l, int t, int r, int b);//绘制单元方格void DrawCell (HDC hdc, int l, int t, int r, int b);//绘制移动方块void DrawGamePlace(HDC hdc, int col, int row); //在客户区绘满单元格void DrawPath(HDC hdc, int w, int h);//迷宫拆墙bool Adj(int x, int y, bool* visited, int col);//判断该单元格是否有没有被访问的相邻单元格bool Adj_NoWall(int x, int y, bool* visited, Wall* wall, int col);//判断该单元格是否有没有被访问的相邻单元格并且周围没有墙可以访问void Replace (HDC hdc, int x, int y, int z, int k);//拆墙(用白色划线替换红色划线)void WriteDocument (MazeEdge* mazeedge, Wall* wall, int i);//将迷宫拆墙数据写入txt文件中bool ReadDocument (HDC hdc);//从txt文件中读取迷宫拆墙数据void DFS (HDC hdc);//深度优先搜索寻找迷宫路径void BFS (HDC hdc);//广度优先搜索寻找迷宫路径//---------------------------------------------------------------int WINAPI WinMain ( HINSTANCE hInstance, HINSTANCE hPrevInstance, PSTR szCmdLine, int iCmdShow){ static char AppName[]="ToyBrick";//窗口类名 HWND hwnd; MSG msg; //消息结构 WNDCLASSEX wndclass; //窗口类 int iScreenWide; //定义一个整型变量来取得窗口的宽度 wndclass.cbSize = sizeof(wndclass); wndclass.style = CS_HREDRAW|CS_VREDRAW;//窗口类型 wndclass.lpfnWndProc = WndProc; //窗口处理函数为 WndProc wndclass.cbClsExtra = 0; //窗口类无扩展 wndclass.cbWndExtra = 0; //窗口实例无扩展 wndclass.hInstance = hInstance; //当前实例句柄 wndclass.hIcon = LoadIcon (NULL, IDI_APPLICATION);//默认图标 wndclass.hCursor = LoadCursor (NULL,IDC_ARROW); //箭头光标 wndclass.hbrBackground = (HBRUSH)GetStockObject (WHITE_BRUSH); //背景为黑色 wndclass.lpszMenuName = NULL; //窗口中无菜单 wndclass.lpszClassName = AppName; //类名为"ToyBrick" wndclass.hIconSm = LoadIcon (NULL, IDI_INFORMATION);//----------------------------------窗口类的注册----------------------------------------- if(!RegisterClassEx (&wndclass))//如果注册失败则发出警报声音，返回FALSE { MessageBeep(0); return FALSE; } // 获取显示器分辨率的X值iScreenWide，将程序窗口置于屏幕中央 iScreenWide=GetSystemMetrics (SM_CXFULLSCREEN); hwnd =CreateWindow ( AppName, //窗口类名 "深度、广度优先搜索迷宫",//窗口实例的标题名 WS_MINIMIZEBOX|WS_SYSMENU , //窗口的风格 iScreenWide/2-W*CELL/2, //窗口左上角横坐标(X) CELL, //窗口左上角纵坐标(Y) (W+0.3)*CELL, //窗口的宽，而不是客户区的宽 (H+1.2)*CELL, //窗口的高 ，而不是客户区的高 NULL, //窗口无父窗口 NULL, //窗口无主菜单 hInstance, //创建此窗口的应用程序的当前句柄 NULL //不使用该值 ); if(!hwnd) return FALSE; MessageBox(NULL,TEXT("主程序:彭俊威"), TEXT("数据结构课程设计"),MB_ICONINFORMATION); //显示窗口 ShowWindow (hwnd,iCmdShow); //绘制客户区 UpdateWindow (hwnd); //消息循环 while (GetMessage (&msg, NULL, 0, 0)) { TranslateMessage (&msg); DispatchMessage (&msg); } //消息循环结束即程序终止时将消息返回系统 return msg.wParam;}//-------------------窗口过程函数WndProc-----------------------------LRESULT CALLBACK WndProc ( HWND hwnd,UINT iMsg,WPARAM wParam,LPARAM lParam ){ HDC hdc; PAINTSTRUCT ps; //char Buffer[20]; switch (iMsg) { //WM_PAINT(窗口第一次生成时执行,WM_PAINT将图从内存拷到屏幕上) case WM_PAINT: hdc =BeginPaint (hwnd, &ps);//获得设备环境句柄 DrawGamePlace(hdc, W, H);//在客户区绘满单元格 if (!ReadDocument(hdc)) DrawPath(hdc, W, H);//拆墙 MessageBox (NULL,TEXT("开始深度优先搜索"), TEXT("搜索方式"), NULL); DFS (hdc);//深度优先搜索寻找迷宫出口 DrawWhiteGround (hdc);//将客户区还原为白色背景 ReadDocument(hdc);//重新绘制迷宫 MessageBox (NULL,TEXT("开始广度优先搜索"), TEXT("搜索方式"), NULL); BFS (hdc);//广度优先搜索寻找迷宫出口 EndPaint (hwnd, &ps); return 0; //WM_DESTROY(响应关闭窗口动作) case WM_DESTROY: PostQuitMessage (0); return 0; } return DefWindowProc (hwnd, iMsg, wParam, lParam);}////将整个客户区绘制为白色void DrawWhiteGround (HDC hdc){int col, row;std::ifstream f ("d:\\迷宫拆墙数据.txt");f>>col>>row;f.close();HBRUSH hbrush = CreateSolidBrush(RGB(255,255,255));SelectObject(hdc, hbrush);Rectangle(hdc, 0, 0, col*CELL, row*CELL);DeleteObject(hbrush);}//绘制迷宫起始点与终止点void DrawRedBlock (HDC hdc, int l, int t, int r, int b){HBRUSH hbrush = CreateSolidBrush(RGB(255,0,0));SelectObject (hdc, hbrush);Rectangle(hdc, l, t, r, b);DeleteObject(hbrush);}//拆墙(用白色划线替换红色划线)void Replace (HDC hdc, int x, int y, int z, int k){ HPEN hpen; hpen = CreatePen(PS_SOLID, 1, RGB(255,255,255)); SelectObject(hdc, hpen); MoveToEx (hdc,x, y,NULL); LineTo (hdc, z, k); DeleteObject(hpen);}//画单元格，后面四个参数依次为左上坐标和右下坐标void DrawRect (HDC hdc, int l, int t, int r, int b){ MoveToEx (hdc, l, t, NULL); //将起始点移动到(l,t) LineTo (hdc, r, t); LineTo (hdc, r, b); LineTo (hdc, l, b); LineTo (hdc, l,t);}//用绿色画刷画移动目标void DrawCell (HDC hdc, int l, int t, int r, int b){ HBRUSH hbrush; hbrush=CreateSolidBrush(RGB(0,255,0)); // 绿色画刷 SelectObject(hdc,hbrush); Rectangle(hdc,l, t, r, b); DeleteObject (hbrush);}//在客户区绘满单元格void DrawGamePlace(HDC hdc, int col, int row){ int i,j; HPEN hpen1; hpen1=CreatePen(PS_SOLID,1,RGB(255,0,0)); //绘制游戏区域方格线(红色) SelectObject(hdc,hpen1); for (i=0; i
            
             Stack; MazeEdge *mazeedge; Wall* wall;//储存每个单元格的墙的情况 wall = new Wall[col*row];//申请col*row个单元格 for (x=0; x
             
              -1)&&!visited[w.index_y*col+w.index_x-1])//左移 { Sleep(50); i++; mazeedge[i].x = w.x;/*记录迷宫的拆墙数据*/ mazeedge[i].y = w.y; mazeedge[i].z = w.x; mazeedge[i].w = w.y+CELL; / /*记录每个单元格四面墙的数据 wall[w.index_y*col+w.index_x].wall_l = 0;//单元格(w.index_x,w.index_y)的左墙被拆除 wall[w.index_y*col+w.index_x-1].wall_r = 0;//单元格(w.index_x-1,w.index_y)的右墙被拆除 Replace (hdc, w.x, w.y, w.x, w.y+CELL);//拆左竖墙，左拆与右拆不一样 visited[w.index_y*col+w.index_x-1] = true;//标记已经访问过的单元格 Stack.push(position[w.index_y*col+w.index_x-1]);//符合条件的相邻单元格进栈 w = Stack.top(); } if (temp==2&&(w.index_y-1>-1)&&!visited[(w.index_y-1)*col+w.index_x])//上移 { Sleep(50); i++; mazeedge[i].x = w.x;/*记录迷宫的拆墙数据*/ mazeedge[i].y = w.y; mazeedge[i].z = w.x+CELL; mazeedge[i].w = w.y; / /*记录每个单元格四面墙的数据 wall[w.index_y*col+w.index_x].wall_t = 0;//单元格(w.index_x,w.index_y)的上墙被拆除 wall[(w.index_y-1)*col+w.index_x].wall_b = 0;//单元格(w.index_x,w.index_y-1)的下墙被拆除 Replace (hdc, w.x, w.y, w.x+CELL, w.y);//拆横墙 visited[(w.index_y-1)*col+w.index_x] = true;//标记已经访问过的单元格 Stack.push(position[(w.index_y-1)*col+w.index_x]);//符合条件的相邻单元格进栈 w = Stack.top(); } if (temp==3&&(w.index_y+1
              
                Stack; std::ifstream f("d:\\迷宫拆墙数据.txt"); /*读迷宫规模数据*/ f>>col>>row;//从txt文件中获取原来迷宫的规模 f.close(); wall = new Wall[col*row]; std::ifstream f1("d:\\每个单元格四面墙的数据.txt"); /*读迷宫墙的信息*/ for (i=0; i
               
                >wall[i].wall_l>>wall[i].wall_t>>wall[i].wall_r>>wall[i].wall_b; f1.close(); srand(time(NULL));//系统时间作随机种子 entrance = rand()%col;//随机在迷宫第一行和最后一行分别产生入口与出口 exit = rand()%col; visited = new bool[col*row];//访问标记 for (i=0; i
                
                  Queue; char Buffer[20]; std::ifstream f("d:\\迷宫拆墙数据.txt"); /*读迷宫规模数据*/ f>>col>>row;//从txt文件中获取原来迷宫的规模 f.close(); wall = new Wall[col*row]; std::ifstream f1("d:\\每个单元格四面墙的数据.txt"); /*读迷宫墙的信息*/ for (i=0; i
                 
                  >wall[i].wall_l>>wall[i].wall_t>>wall[i].wall_r>>wall[i].wall_b; f1.close(); srand(time(NULL));//系统时间作随机种子 entrance = rand()%col;//随机在迷宫第一行和最后一行分别产生入口与出口 exit = rand()%col; visited = new bool[col*row];//访问标记 for (i=0; i
                  
                   -1)&&!visited[u.index_y*col+u.index_x-1]&&wall[u.index_y*col+u.index_x].wall_l==0)//如果作相邻单元格没有被访问过，并且可以被访问 { Sleep (100); DrawCell (hdc, u.x-CELL+6, u.y+6, u.x-6, u.y+CELL-6);//画左单元格 visited[u.index_y*col+u.index_x-1] = true; Queue.push (position[u.index_y*col+u.index_x-1]);//左单元格进队列 } if ((u.index_x+1
                   
                    -1)&&!visited[(u.index_y-1)*col+u.index_x]&&wall[u.index_y*col+u.index_x].wall_t==0) { Sleep (100); DrawCell (hdc, u.x+6, u.y+CELL+6, u.x+CELL-6, u.y+2*CELL-6);//画上单元格 visited[(u.index_y-1)*col+u.index_x] = true; Queue.push (position[(u.index_y-1)*col+u.index_x]);//上单元格进队列 } if (u.index_y==row-1&&u.index_x==exit)//如果到达迷宫出口则停止搜索 { DrawRedBlock (hdc, exit*CELL+6, (row-1)*CELL+6, (exit+1)*CELL-6, row*CELL-6);//绘制迷宫出口 MessageBox(NULL,TEXT("成功走出迷宫!"), TEXT("Congratunations"),MB_ICONINFORMATION); break; } } }}//判断该单元格是否有没有被访问的相邻单元格bool Adj(int x, int y, bool* visited, int col){ if((x-1>-1)&&!visited[y*col+x-1]||(x+1
                    
                     -1&&!visited[(y-1)*col+x]||y+1
                     
                      -1)&&!visited[y*col+x-1]&&wall[y*col+x].wall_l==0||(x+1
                      
                       -1&&!visited[(y-1)*col+x]&&wall[y*col+x].wall_t==0||y+1
                       
                        >col>>row;f.close();}DrawGamePlace(hdc, col, row);//在客户区绘满红色单元格mazeedge = new MazeEdge[col*row-1];f.open("d:\\迷宫拆墙数据.txt");f>>col>>row;for (i=0; i
                        
                         >mazeedge[i].x>>mazeedge[i].y>>\mazeedge[i].z>>mazeedge[i].w;f.close();for (i=0; i

程序非原创，在开源中国有类似的。

基于c++win32编程。

转载于:https://www.cnblogs.com/pengjunwei/p/3804623.html

你可能感兴趣的文章