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