//------------ Mouse in a Maze (C++ Builder) by S. J. Shyu --------------------

bool found = false;

#define possible_direction 8

struct offset

{  int dx, dy;

};

enum directions {N, NE, E, SE, S, SW, W, NW};  // N=0, NE=1, ... , NW=7; Using integers 0-7 would be just fine (No need to enumerate them)

struct offset move[possible_direction];

struct position

{  int x,y;

   directions dir;   // Or int dir;

};

int m, p, top = -1;

position Stack [200];

int mark[200][200];

// int maze [100][100];

int * * maze;

int * * g_maze;

int g_Heigh, Heigh,  g_Width, Width;

AnsiString str = "";

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner) : TForm(Owner)

{   Memo1->Clear();

    move[N].dx = -1;   move[N].dy = 0; //  Define offset here!

    move[NE].dx = -1;  move[NE].dy = 1;

    move[E].dx = 0;    move[E].dy = 1;

    move[SE].dx = 1;   move[SE].dy = 1;

    move[S].dx = 1;    move[S].dy = 0;

    move[SW].dx = 1;   move[SW].dy = -1;

    move[W].dx = 0;    move[W].dy = -1;

    move[NW].dx = -1;  move[NW].dy = -1;

}

//---------------------------------------------------------------------------

void push (struct position data)

{ if (top == (m*p-1)) ; //StackFull();

else Stack[++top] = data;

}

struct position pop()

{ if (top == -1)

{  position step;

  step.x = -1;    step.y = -1;    step.dir = N;  

  return step; //StackEmpty();

}

else

{    return Stack[top--];

}

}

int** generatemaze(int** maze, int x,int y)

{ // generate Maze here

return maze;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)

{ //------------寫檔範例--------------

if (SaveDialog1->Execute())     //確認SaveDialog1讀取檔案成功

{ //-------------------------

//抓取SaveDialog1所開啟的檔案名稱, 將檔案名稱轉為char格式後用fopen開啟此檔案

//--String fileName = SaveDialog1->FileName;

//--char* ch_Filename = fileName.c_str();

AnsiString file_name = SaveDialog1->FileName;

FILE *fp = fopen(file_name.c_str(),"w");    // "w" 表示開以寫檔的方式開啟

//利用fprintf將g_matrix中的元素寫入fp, 當需要換行時使用putc將'\n'加入fp中

            if (fp)

            { fprintf(fp, "%d %d", g_Heigh, g_Width);

                putc('\n', fp);

for (int i=0 ; i<g_Heigh ; i++)

{       for (int j=0 ; j<g_Width ; j++)

                    { fprintf(fp, "%d ", g_maze[i][j]);

                     }

                        putc('\n', fp);

                }

                fclose(fp);   // 寫完檔後請關檔

            }

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button3Click(TObject *Sender)

{ //------------開檔範例--------------

int temp, grid_Size ;

char fileChar;

int** maze;

if (OpenDialog1->Execute())     //確認 OpenDialog1 有執行開檔

{  //-------------------------

//抓取OpenDialog1所開啟的檔案名稱, 將檔案名稱轉為char格式後用fopen開啟此檔案

//--String fileName = OpenDialog1->FileName;

//--char* ch_Filename = fileName.c_str();

AnsiString file_name = OpenDialog1->FileName;

FILE *fp = fopen(file_name.c_str(),"r");    // "r" 表示開以讀檔的方式開啟

int Heigh,Width; 

int i=0, j=0;

if (fp)

          { fscanf(fp,"%d %d",&Heigh,&Width);  //用fscanf掃描檔案的第一行, 抓取matrix的大小(n, m)

                 String str;

                int** maze = new int* [Heigh];

                for  (int a=0 ; a<Heigh ; a++)

{          maze[a] = new int [Width];

                 }

//同樣用fscanf掃描接下來的文件,並將文件的資料存入matrix

                //" %c"為以char形態讀取, %c前的空格代表不讀取無意義的值(如:空白, \n)

//當fscanf回傳EOF(end of file)時則代表檔案掃瞄完畢

                while (fscanf(fp, " %c", &fileChar)!=EOF)

                { maze[i][j] = atoi(&fileChar);    //利用atoi函式將char轉為int

j++;

                     if (j == Width)     //i, j為判斷陣列位置的變數

                     {     j=0;      i++;

                     }

                }

                //print

str="";

                Memo1->Lines->Add("===========Maze(H:"+IntToStr(Heigh)+" W:"+IntToStr(Width)+")===========");

                for (i=0 ; i<Heigh ; i++)

                { for (str="", j=0 ; j<Width ; j++)

                        { str += "  "+IntToStr(maze[i][j]);

                        }

                        Memo1->Lines->Add(str); 

}

//將matrix與其大小傳入全域變數

                g_maze = maze;

g_Heigh = Heigh;

                g_Width = Width;

StringGrid1->ColCount = g_Width;

StringGrid1->RowCount = g_Heigh;

StringGrid1->FixedCols = 0;

StringGrid1->FixedRows = 0;

for (i=0; i<g_Width; i++) StringGrid1->ColWidths[i] = grid_Size ;

for (i=0; i<g_Heigh; i++) StringGrid1->RowHeights[i] = grid_Size ;

StringGrid2->ColCount = g_Width;

StringGrid2->RowCount = g_Heigh;

StringGrid2->FixedCols = 0;

StringGrid2->FixedRows = 0;

for (int i=0; i<g_Width; i++) StringGrid2->ColWidths[i] = grid_Size ; // grid_Size  may be read from Edit!!

for (int i=0; i<g_Heigh; i++) StringGrid2->RowHeights[i] = grid_Size ;

//mark = maze;

for (int i=0; i<Heigh; i++)

{   for (int j=0; j<Width; j++)

{   mark[i][j] = maze[i][j];

StringGrid1->Cells[j][i] = maze[i][j];

StringGrid2->Cells[j][i] = maze[i][j];

}

}

StringGrid1->Refresh();

StringGrid2->Refresh();

               fclose(fp);   // 讀完檔後請關檔

}

Edit1->Text = Heigh;

Edit2->Text = Width;

        }

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button7Click(TObject *Sender)

{

autoflag = true;

int u, v, i, j;

position step;

// int ** maze;

found = false;

m = g_Heigh-2;

p = g_Width-2;

maze = g_maze;

Memo1->Lines->Add("m="+IntToStr(m)+" p="+IntToStr(p));

for (i=0; i<=m+1; i++)

{   for (j=0; j<=p+1; j++)

{   mark[i][j] = maze[i][j];

StringGrid1->Cells[j][i] = maze[i][j];

StringGrid2->Cells[j][i] = maze[i][j];

}

}

StringGrid1->Refresh();

StringGrid2->Refresh();

// for (i=0; i<=m+1; i++) { mark[i][0] = 2; mark[i][p+1] = 2; }

// for (j=1; i<=p; i++) { mark[0][j] = 2; mark[m+1][j] = 2; }

Memo1->Lines->Add("===========Mark(m:"+IntToStr(m)+" p:"+IntToStr(p)+")===========");

for (i=0 ; i<m+2 ; i++)

{ for (str="", j=0 ; j<p+2 ; j++)

{ str += " "+IntToStr(mark[i][j]);

}

Memo1->Lines->Add(str);

}

mark[1][0] = 3;

StringGrid1->Cells[0][1] = "*";

StringGrid2->Cells[0][1] = "3";

step.x = 1;

step.y = 1;

step.dir = 2;   // Or step.dir = E;  (i, j, dir) = (1, 1, E)

push(step);

mark[1][1] = 3;

StringGrid1->Cells[1][1] = "*";  StringGrid2->Cells[1][1] = "3";

Sleep(50+((TrackBar1->Position)*10));

while (top != -1)

{ step = pop();

//  dir = step.dir;

while ((step.dir <= 7) && (!found))

{ u = step.x+move[step.dir].dx;

v = step.y+move[step.dir].dy;

// (u, v) = 自 (i, j) 欲嘗試的下一步座標

if  ((maze[u][v]==0) && (mark[u][v]==0)) //(u,v)可以走，且不曾走過

{ mark[u][v] = 3;

push(step);

StringGrid1->Cells[step.y][step.x] = "*";   StringGrid1->Refresh();

StringGrid2->Cells[step.y][step.x] = "3"; StringGrid2->Refresh();

   Sleep(50+((TrackBar1->Position)*10));

if  ((u == m) && (v == p))

{  found = true; //成功找到出口，輸出路徑，可以停止

step.x = u;  step.y = v+1;  step.dir = 2;    // 這是老師的設定，請視各自的情況而定

push(step);

StringGrid1->Cells[v][u] = "@";   StringGrid1->Cells[v+1][u] = "@";

StringGrid2->Cells[v][u] = "4";   StringGrid2->Cells[v+1][u] = "4";

StringGrid1->Refresh(); StringGrid2->Refresh();

for (i=0; i<=m+1; i++)

{   for (j=0; j<=p+1; j++)

{   mark[i][j] = maze[i][j];

}

}

mark[u][v+1] = 3;     // extra exit cell

mark[u][v] = 3;

DrawGrid2->Refresh();

while (top != -1)

{  step = pop();

mark[step.x][step.y] = 3;

  StringGrid1->Cells[step.y][step.x] = "@";

  StringGrid2->Cells[step.y][step.x] = "4";

  StringGrid1->Refresh();    StringGrid2->Refresh();

  Sleep(50+((TrackBar1->Position)*10));

}

Memo1->Lines->Add(str);

}

else

{ step.x = u; step.y = v; step.dir = 0;

}

}

else

{ step.dir = step.dir+1;

}

}

}

//出入口設為走過的路徑； 這是老師的設定，請視各自的情況而定

mark[1][0] = 3;

mark[g_Heigh-2][g_Width-1] = 3;

StringGrid1->Cells[0][1] = "@";

StringGrid2->Cells[0][1] = "4";

AnsiString str="";

Memo1->Lines->Add("===========Mark(m:"+IntToStr(m)+" p:"+IntToStr(p)+")===========");

for (i=0 ; i<m+2 ; i++)

{ for (str="", j=0 ; j<p+2 ; j++)

{ str += " "+IntToStr(mark[i][j]);

}

Memo1->Lines->Add(str);

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::StringGrid1DrawCell(TObject *Sender, int ACol, int ARow, TRect &Rect,

  TGridDrawState State)

{ // StringGrid1->ColCount = g_Width;

// StringGrid1->RowCount = g_Heigh;

AnsiString data = StringGrid1->Cells[ACol][ARow];

if (data == "2") StringGrid1->Canvas->Brush->Color = RGB(100, 25, 55) ;

else if (data == "1") StringGrid1->Canvas->Brush->Color = RGB(20, 20, 20);

else StringGrid1->Canvas->Brush->Color = RGB(250, 245, 135);// (RGB(200, 205, 155));

StringGrid1->Canvas->FillRect(Rect);

if (found && data == "@") StringGrid1->Canvas->TextRect(Rect, Rect.Left+10, Rect.Top+10, data);

else if (data == "*") StringGrid1->Canvas->TextRect(Rect, Rect.Left+10, Rect.Top+10, data);

}

void __fastcall TForm1::StringGrid2DrawCell(TObject *Sender, int ACol, int ARow, TRect &Rect,

  TGridDrawState State)

{ AnsiString data = StringGrid2->Cells[ACol][ARow];

if (data == "4") StringGrid2->Canvas->Brush->Color = RGB(240, 190, 143) ;

else if (data == "3") StringGrid2->Canvas->Brush->Color = RGB(238, 233, 198) ;

else if (data == "2") StringGrid2->Canvas->Brush->Color = RGB(39, 37, 61) ;

else if (data == "1") StringGrid2->Canvas->Brush->Color = RGB(50, 78, 81) ;

else StringGrid2->Canvas->Brush->Color = RGB(228, 247, 238);// (RGB(200, 205, 155));

StringGrid2->Canvas->FillRect(Rect);

}

//---------------------------------------------------------------------------

//------------ Mouse in a Maze (Visual Studio C++) by S. J. Shyu -----------------

#define MaxStack 1000

struct offset

{    int x, y;

};

enum direction {E,S,W,N};    // 4 directions are considered

struct position

{    int x, y;

     direction dir;

};

position stack [MaxStack];

int top;

void push(position step)

{   if (top == g_Height*g_Width) listBox1->Items->Add("Stack is full");

    else stack[++top] = step;

}

position pop()

{   if (top == -1) listBox1->Items->Add("Stack is empty");

    else return stack[top--];

}

void MouseInMaze(int **maze, int Height, int Width)

{   int i, j, u, v;

    bool found = false;

    offset move[4];        // offsets of all 4 directions are prepared

    move[E].x = 0; move[E].y = 1;

    move[S].x = 1; move[S].y = 0;

    move[W].x = 0; move[W].y = -1;

    move[N].x = -1; move[N].y = 0;

    position step;

    maze[1][0] = 3;

    step.x = 1; step.y = 1; step.dir = E;     // define the first step

    maze[1][1] = 3;

    dataGridView1->Rows[1]->Cells[0]->Style->BackColor = Color::SkyBlue;

    if (checkBox1->Checked == true) dataGridView1->Refresh();

    dataGridView1->Rows[1]->Cells[1]->Style->BackColor = Color::SkyBlue;

    if (checkBox1->Checked == true) dataGridView1->Refresh();

    push(step);

    while (top != -1 && !found)     // keep moving till stack empty OR found

    {   step = pop();

        i = step.x; j = step.y; step.dir = step.dir;

        while (step.dir <= N && !found)

        {   u = i + move[step.dir].x;

            v = j + move[step.dir].y;

            if (u == Height - 2 && v == Width - 2)    // whether the EXIT is found

            { found = true;

                step.x = i; step.y = j;

                push(step);

                maze[u][v] = 3;

                dataGridView1->Rows[u]->Cells[v]->Style->BackColor = Color::SkyBlue;

                if (checkBox1->Checked == true) dataGridView1->Refresh();

                while (top != -1)        // all positions in stack constitute the tour from entrance to exit

                {   position s = pop();

                    listBox1->Items->Add("Step:(" + s.x + "," + s.y + ")");

                }

                // return maze;

            }

            if (maze[u][v] == 0)       // a feasible step has been found

            { maze[u][v] = 3;        // mark this position

                dataGridView1->Rows[u]->Cells[v]->Style->BackColor = Color::SkyBlue; //Gray;

                if (checkBox1->Checked == true) dataGridView1->Refresh();

                step.x = i; step.y = j; step.dir = direction(step.dir + 1);

                push(step);                // push previous position/next direction into stack

                i = u; j = v; step.dir = E;// move to the feasible position

            }

            else

                step.dir = direction(step.dir + 1);

        }

        dataGridView1->Rows[i]->Cells[j]->Style->BackColor = Color::PowderBlue;

        // no more feasible step for this position

        if (checkBox1->Checked == true) dataGridView1->Refresh();

    }

    // return maze;

}

======================================= Visual Studio 2022 ====================================

#include<cstdlib>

#include<string>

#include<time.h>

#define MaxStack 1000

struct offset

{

int x, y;

};

enum direction{E, S, W, N}; // 有右、下、左、上四個方向

struct position

{

int x, y;

direction dir;

};

position stack[MaxStack];

int top = -1;

int** maze = NULL;

int width = 0;

int height = 0;

// 以上為Global Variables

void draw_dataGridView()

{

tabControl1->SelectTab(1); // 跳轉到第二個分頁(tabPage)

dataGridView2->RowCount = height + 1; // 要多加 1，不然他會IndexOutOfRange，可能是dataGridView本身的設定問題

dataGridView2->ColumnCount = width;

dataGridView2->ColumnHeadersVisible = false; // 隱藏columns

dataGridView2->RowHeadersVisible = false; // 隱藏index

dataGridView2->AllowUserToAddRows = false; // 去掉最後一行空白行

//dataGridView2->AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.Fill; // 調整欄位寬度，但不知為何這邊沒辦法用這行程式，所以手動去更改屬性的地方

for (int i = 0; i < height; i++)

{

for (int j = 0; j < width; j++)

{

if (maze[i][j] == 2) // 外牆塗深紅色

{

dataGridView2->Rows[i]->Cells[j]->Style->BackColor = Color::DarkRed;

}

else if (maze[i][j] == 1) // 迷宮內牆塗黑色

{

dataGridView2->Rows[i]->Cells[j]->Style->BackColor = Color::Black;

}

else if (maze[i][j] == 0) // 通道塗黃色

{

dataGridView2->Rows[i]->Cells[j]->Style->BackColor = Color::LightYellow;

}

}

}

// 下面兩行程式碼負責移除選取時會有的藍色框框，可以註解看看變化

dataGridView2->DefaultCellStyle->SelectionBackColor = Color::DarkRed;

dataGridView2->DefaultCellStyle->SelectionForeColor = Color::White;

}

void push(position step)

{

if (top == MaxStack)

{

listBox1->Items->Add("Stack is full !");

}

else 

{

stack[++top] = step;

}

}

position pop()

{

if (top == -1)

{

listBox1->Items->Add("Stack is empty.");

}

else

{

return stack[top--];

}

}

// Mouse in Maze 主程式

private: System::Void button2_Click(System::Object^ sender, System::EventArgs^ e) 

{

int i, j, u, v;

bool found = false;

offset move[4]; // 4個方向的移動

move[E].x = 0; move[E].y = 1;

move[S].x = 1; move[S].y = 0;

move[W].x = 0; move[W].y = -1;

move[N].x = -1; move[N].y = 0;

position step;

maze[1][0] = 3; // 入口先標示走過了

step.x = 1; step.y = 1; step.dir = E; // 第一步，往右從(1, 0)到(1, 1)

maze[1][1] = 3; 

dataGridView2->Rows[1]->Cells[0]->Style->BackColor = Color::DarkGreen;

if (checkBox1->Checked == true)

dataGridView2->Refresh();

dataGridView2->Rows[1]->Cells[1]->Style->BackColor = Color::DarkGreen;

if (checkBox1->Checked == true)

dataGridView2->Refresh();

push(step);

while (top != -1 && !found) // 找到路徑或是stack為空(無路可走)時就停下來

{

step = pop();

i = step.x; j = step.y;

while (step.dir <= N && !found)

{

// (u, v) = 從(i, j)想要嘗試的下一步座標

u = i + move[step.dir].x;

v = j + move[step.dir].y;

if (u == height - 2 && v == width - 1)

{

found = true; // 成功找到出口

step.x = u; step.y = v; step.dir = E; 

push(step);

maze[u][v] = 3;

dataGridView2->Rows[u]->Cells[v]->Style->BackColor = Color::DarkGreen;

if (checkBox1->Checked == true)

dataGridView2->Refresh();

while (top != -1) // 所有在stack的step組成了tour

{

position s = pop();

listBox1->Items->Add("Step(" + s.x + "," + s.y + ")");

}

}

if (maze[u][v] == 0) // (u,v)可以走，且沒有被走過

{

maze[u][v] = 3;

dataGridView2->Rows[u]->Cells[v]->Style->BackColor = Color::DarkGreen;

if (checkBox1->Checked == true)

dataGridView2->Refresh();

step.x = i, step.y = j; step.dir = direction(step.dir + 1);

push(step);

i = u; j = v; step.dir = E;

}

else

{

step.dir = direction(step.dir + 1);

}

}

if (!found)

{

dataGridView2->Rows[i]->Cells[j]->Style->BackColor = Color::LightGreen;

if(checkBox1->Checked == true)

dataGridView2->Refresh();

}

}

}