基于深度及廣度優先搜索的迷宮問題的演示

2019-11-17 03:26:27
字體：大中小
來源：轉載
供稿：網友
1 時間復雜度分析

由于該圖采用鄰接矩陣存儲，整個算法遍歷的過程所花費的時間復雜度為該矩陣的N(row*col)。而由于其需要分別訪問已經定位，需要進行分別2次操作，如下：
visited = new bool[col*row];//訪問標記
for (i=0; i<row; i++)
for (j=0; j<col; j++)
visited[i*col+j] = false;//初始為未訪問狀態
position = new POSITION[col*row];
for (i=0; i<row; i++)//給每個點定位
for (j=0; j<col; j++)
{
position[i*col+j].x = j*CELL;
position[i*col+j].y = i*CELL;
position[i*col+j].index_x = j;
position[i*col+j].index_y = 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<windows.h>#include<iostream>#include<ctime>#include<stdlib.h>#include<fstream>#include<stack>#include<queue>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<row; i++)  for(j=0; j<col; j++)   DrawRect (hdc, j*CELL, i*CELL, (j+1)*CELL, (i+1)*CELL);    DeleteObject(hpen1);}//迷宮拆墻void DrawPath(HDC hdc, int col, int row){    int x, y, temp, i(-1);    bool* visited;                // 訪問標記    POSITION* position;//儲存每個單元格的坐標    POSITION w;    std::stack<POSITION>Stack;    MazeEdge *mazeedge;    Wall* wall;//儲存每個單元格的墻的情況    wall = new Wall[col*row];//申請col*row個單元格    for (x=0; x<row; x++)//請所有單元格的四面墻初始化為都有狀態        for (y=0; y<col; y++)        {            wall[x*col+y].wall_l = 1;            wall[x*col+y].wall_t = 1;            wall[x*col+y].wall_r = 1;            wall[x*col+y].wall_b = 1;        }    visited = new bool[col*row];//訪問標記    for (x=0; x<row; x++)        for (y=0; y<col; y++)            visited[x*col+y] = false;//初始為未訪問狀態        position = new POSITION[col*row];    for (x=0; x<row; x++)//給每個點定位        for (y=0; y<col; y++)        {            position[x*col+y].x = y*CELL;            position[x*col+y].y = x*CELL;            position[x*col+y].index_x = y;            position[x*col+y].index_y = x;        }   mazeedge = new MazeEdge[col*row-1];//一棵樹有頂點數-1條邊   MessageBox(NULL, TEXT("現在開始拆墻"), TEXT("消息"), NULL);   srand (time(NULL));//系統時間作隨機種子   x = rand()%col;//隨機產生起始點   y = rand()%row;   Stack.push(position[y*col+x]);//迷宮入口進棧   visited[y*col+x] = true;//標記已經訪問過   while (!Stack.empty())   {   w = Stack.top();   while (Adj(w.index_x, w.index_y, visited, col))//如果該單元格有沒有被訪問過的單元格   {       temp = rand()%4;   if (temp==0&&(w.index_x+1<col)&&!visited[w.index_y*col+w.index_x+1])//右移   {       Sleep(50);       i++;       mazeedge[i].x = w.x+CELL;/*記錄迷宮的拆墻數據*/       mazeedge[i].y = w.y;       mazeedge[i].z = w.x+CELL;       mazeedge[i].w = w.y+CELL;       /////////////////////////                 /*記錄每個單元格四面墻的數據       wall[w.index_y*col+w.index_x].wall_r = 0;//單元格(w.index_x,w.index_y)的右墻被拆除       wall[w.index_y*col+w.index_x+1].wall_l = 0;//單元格(w.index_x+1,w.index_y)的左墻被拆除       ////////////////////////       Replace (hdc, w.x+CELL, w.y, w.x+CELL, 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==1&&(w.index_x-1>-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<row)&&!visited[(w.index_y+1)*col+w.index_x])//下移   {       Sleep(50);       i++;       mazeedge[i].x = w.x;/*記錄迷宮的拆墻數據*/       mazeedge[i].y = w.y+CELL;       mazeedge[i].z = w.x+CELL;       mazeedge[i].w = w.y+CELL;        /////////////////////////                 /*記錄每個單元格四面墻的數據       wall[w.index_y*col+w.index_x].wall_b = 0;//單元格(w.index_x,w.index_y)的下墻被拆除       wall[(w.index_y+1)*col+w.index_x].wall_t = 0;//單元格(w.index_x,w.index_y+1)的上墻被拆除       ////////////////////////       Replace (hdc, w.x, w.y+CELL, w.x+CELL, w.y+CELL);//拆橫墻       visited[(w.index_y+1)*col+w.index_x] = true;//標記已經訪問過的單元格       Stack.push(position[(w.index_y+1)*col+w.index_x]);//符合條件的相鄰單元格進棧       w = Stack.top();   }   }   Stack.pop();//回溯}   WriteDocument(mazeedge, wall, i);//將迷宮拆墻數據寫入txt文件}//深度優先搜索尋找迷宮路徑void DFS (HDC hdc){    int col, row, entrance, exit, i, j;    bool* visited = NULL;//訪問標示    bool status(false);//走迷宮狀態    POSITION* position = NULL;//記錄各個單元的坐標    POSITION w;//臨時中間變量    Wall* wall = NULL;//儲存單元格四面墻的信息    std::stack<POSITION> 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<col*row; i++)//從txt文檔中讀入每個單元格四面墻數據        f1>>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<row; i++)    for (j=0; j<col; j++)    visited[i*col+j] = false;//初始為未訪問狀態    position = new POSITION[col*row];    for (i=0; i<row; i++)//給每個點定位    for (j=0; j<col; j++)    {    position[i*col+j].x = j*CELL;    position[i*col+j].y = i*CELL;    position[i*col+j].index_x = j;    position[i*col+j].index_y = i;    }    Stack.push(position[entrance]);//迷宮入口進棧    visited[entrance] = true;    DrawRedBlock (hdc, entrance*CELL+6, 6, (entrance+1)*CELL-6, CELL-6);//繪制迷宮入口    DrawRedBlock (hdc, exit*CELL+6, (row-1)*CELL+6, (exit+1)*CELL-6, row*CELL-6);//繪制迷宮出口    while (!Stack.empty()&&!status)    {     w = Stack.top();     while (Adj_NoWall (w.index_x, w.index_y, visited, wall, col))//如果有還沒有被訪問的相鄰單元格并且可以訪問     {       if (wall[w.index_y*col+w.index_x].wall_b == 0&&!visited[(w.index_y+1)*col+w.index_x])//如果下墻已經被拆除而且下邊單元格沒有被訪問過,目標下移      {          Sleep(200);      DrawCell (hdc, w.x+6, w.y+CELL+6, w.x+CELL-6, w.y+2*CELL-6);//使移動目標小于單元格大小      visited[(w.index_y+1)*col+w.index_x] = true;      Stack.push(position[(w.index_y+1)*col+w.index_x]);//入棧      w = Stack.top();      }      else if (wall[w.index_y*col+w.index_x].wall_r == 0&&!visited[(w.index_y)*col+w.index_x+1])//如果右墻已經被拆除而且右邊單元格沒有被訪問過,目標右移      {          Sleep(200);      DrawCell (hdc, w.x+CELL+6, w.y+6, w.x+2*CELL-6, w.y+CELL-6);//使移動目標小于單元格大小      visited[w.index_y*col+w.index_x+1] = true;      Stack.push(position[w.index_y*col+w.index_x+1]);//入棧      w = Stack.top();      }      else if (wall[w.index_y*col+w.index_x].wall_l == 0&&!visited[w.index_y*col+w.index_x-1])//如果左墻已經被拆除而且左邊單元格沒有被訪問過,目標左移      {          Sleep(200);      DrawCell (hdc, w.x-CELL+6, w.y+6, w.x-6, w.y+CELL-6);//使移動目標小于單元格大小      visited[w.index_y*col+w.index_x-1] = true;      Stack.push(position[w.index_y*col+w.index_x-1]);//入棧      w = Stack.top();      }     else if (wall[w.index_y*col+w.index_x].wall_t == 0&&!visited[(w.index_y-1)*col+w.index_x])//如果上墻已經被拆除而且上邊單元格沒有被訪問過,目標上移      {          Sleep(200);      DrawCell (hdc, w.x+6, w.y-CELL+6, w.x+CELL-6, w.y-6);//使移動目標小于單元格大小      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 (w.index_y==row-1&&w.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);          status = true;          break;      }     }Stack.pop();//回溯}}//廣度優先搜索尋找迷宮路徑void BFS (HDC hdc){    int col, row, entrance, exit, i, j;    bool* visited = NULL;//訪問標示    bool status(false);//走迷宮狀態    POSITION* position = NULL;//記錄各個單元的坐標    POSITION u;//臨時中間變量    Wall* wall = NULL;//儲存單元格四面墻的信息    std::queue<POSITION> 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<col*row; i++)//從txt文檔中讀入每個單元格四面墻數據        f1>>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<row; i++)    for (j=0; j<col; j++)    visited[i*col+j] = false;//初始為未訪問狀態    position = new POSITION[col*row];    for (i=0; i<row; i++)//給每個點定位    for (j=0; j<col; j++)    {    position[i*col+j].x = j*CELL;    position[i*col+j].y = i*CELL;    position[i*col+j].index_x = j;    position[i*col+j].index_y = i;    }    Queue.push(position[entrance]);//迷宮入口進隊列    visited[entrance] = true;    DrawRedBlock (hdc, entrance*CELL+6, 6, (entrance+1)*CELL-6, CELL-6);//繪制迷宮入口    DrawRedBlock (hdc, exit*CELL+6, (row-1)*CELL+6, (exit+1)*CELL-6, row*CELL-6);//繪制迷宮出口    while (!Queue.empty())    {     u = Queue.front();     Queue.pop();     if (Adj_NoWall (u.index_x, u.index_y, visited, wall, col))//如果有還沒有被訪問的相鄰單元格并且可以訪問     {      if ((u.index_y+1<row)&&!visited[(u.index_y+1)*col+u.index_x]&&wall[u.index_y*col+u.index_x].wall_b==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_x-1>-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<col)&&!visited[u.index_y*col+u.index_x+1]&&wall[u.index_y*col+u.index_x].wall_r==0)//如果作相鄰單元格沒有被訪問過，并且可以被訪問      {           Sleep (100);      DrawCell (hdc, u.x+CELL+6, u.y+6, u.x+2*CELL-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_y-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<W)&&!visited[y*col+x+1]||/     y-1>-1&&!visited[(y-1)*col+x]||y+1<H&&!visited[(y+1)*col+x])       return true;   return false;}//判斷該單元格是否有沒有被訪問的相鄰單元格并且周圍沒有墻可以訪問bool Adj_NoWall(int x, int y, bool* visited, Wall* wall, int col){ if((x-1>-1)&&!visited[y*col+x-1]&&wall[y*col+x].wall_l==0||(x+1<W)&&!visited[y*col+x+1]&&wall[y*col+x].wall_r==0||/     y-1>-1&&!visited[(y-1)*col+x]&&wall[y*col+x].wall_t==0||y+1<H&&!visited[(y+1)*col+x]&&wall[y*col+x].wall_b==0)       return true;   return false;}//將迷宮拆墻數據寫入txt文件中void WriteDocument (MazeEdge* mazeedge, Wall* wall, int i){int j;std::ofstream f("d://迷宮拆墻數據.txt");f<<W<<" "<<H<<std::endl;//寫入拆墻數據for (j=0; j<i+1; j++)f<<mazeedge[j].x<<" "<<mazeedge[j].y<<" "/<<mazeedge[j].z<<" "<<mazeedge[j].w<<std::endl;f.close();std::ofstream f1("d://每個單元格四面墻的數據.txt");//寫入每個單元格四面墻的數據for (j=0; j<i+2; j++)f1<<wall[j].wall_l<<" "<<wall[j].wall_t<<" "/<<wall[j].wall_r<<" "<<wall[j].wall_b<<std::endl;f1.close();}//從txt文件中讀取迷宮拆墻數據bool ReadDocument (HDC hdc){int col, row, i;MazeEdge *mazeedge;std::ifstream f ("d://迷宮拆墻數據.txt");if (f.fail())//打開文件失敗return false;else{f>>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<col*row-1; i++)//從txt文檔中讀入數據f>>mazeedge[i].x>>mazeedge[i].y>>/mazeedge[i].z>>mazeedge[i].w;f.close();for (i=0; i<col*row-1; i++)//拆墻Replace(hdc, mazeedge[i].x, mazeedge[i].y, mazeedge[i].z, mazeedge[i].w);return true;}