30-1 Mouse in a Maze (VS C++)

#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;

}