C# 老鼠走迷宮

作者：貓貓風 ฅ●ω●ฅ│2018-12-08 21:49:43│巴幣：32│人氣：2749

這主題應該算是資料結構常常會出的經典問題

主要有兩種解法，一是遞迴(recursive) 二是堆疊(Stack)

本篇採用Stack的寫法來實作老鼠走迷宮

原理非常簡單，將走過的路徑存到Stack中

如果遇到死路則將Stack中紀錄的路徑返還，然後繼續尋找其他沒有走過的路

重複上述方式直到找到終點

以下為實作程式碼，迷宮可自行繪製，不過迷宮尺寸也要隨著迷宮大小一併修改

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;
using System.Threading;
namespace Maze
{
public partial class Form1 : Form
{
private Label[] _label_wall = new Label[1000];
private Label[] _label_path = new Label[1000];
private Label[] _label_step = new Label[1000];
private Label[] _label_obj = new Label[1];
private Label[] _label_Exit = new Label[1];
private int _label_wall_x = 30, _label_wall_y = 30, _label_path_x =
30,_label_path_y = 30,
_label_obj_x = 90, _label_obj_y = 60;
int _label_step_index = 0;
Stack _st = new Stack();
private Thread _th;
private delegate void UpdateUI(parameter.status current, Control ctl);//宣告委派
int pre_x;
int pre_y;
bool first = true;
int[] _record = new int[1000];
int index =1;
int r_count = 0, l_count = 0, u_count = 0, d_count = 0, _pre_index = 0;
bool _check = true;
/*int[] _maze = {
1,0,1,1,1,
1,0,0,1,0,
1,0,0,0,1,
1,0,1,0,1,
1,1,1,0,1,
1,0,0,0,1,
1,0,1,0,1,
1,0,1,1,1
};*/
/*int[] _maze = {
1,0,1,1,1,
1,0,0,1,0,
1,0,0,0,1,
1,0,1,0,1,
1,1,1,0,1,
1,0,0,0,1,
1,0,1,0,1,
1,0,1,1,1,
1,0,0,1,1,
1,0,0,0,1,
1,0,1,0,1,
1,1,0,0,1,
1,0,0,1,1,
1,0,1,1,1
};*/
int _row = 12;
/*int[] _maze = {
1,0,1,1,1,1,1,
1,0,0,1,0,0,1,
1,0,0,0,0,0,1,
1,0,1,0,0,0,1,
1,0,1,0,0,0,1,
1,0,0,0,0,1,1,
1,0,1,0,0,1,1,
1,0,1,1,0,1,1,
1,0,1,1,0,1,1,
1,0,1,0,1,0,1,
1,0,0,0,0,0,1,
1,1,0,1,1,0,1,
1,0,0,0,0,0,1,
1,0,1,1,1,1,1
};*/
/*int[] _maze = {
1,0,1,1,1,1,1,
1,0,0,1,0,0,1,
1,0,0,0,0,0,1,
1,1,1,0,1,0,1,
1,0,1,0,1,0,1,
1,1,0,0,0,1,1,
1,0,0,0,0,1,1,
1,0,1,1,1,1,1,
1,0,0,0,0,1,1,
1,0,1,1,1,0,1,
1,0,0,0,0,0,1,
1,1,1,1,1,0,1,
1,0,0,0,0,0,1,
1,0,1,1,1,1,1
};*/
/*int[] _maze = {
1,0,1,1,1,1,1,1,1,1,
1,0,0,0,0,1,0,0,0,1,
1,0,1,0,0,0,1,0,0,1,
1,0,1,0,1,0,1,0,0,1,
1,0,0,0,1,0,1,0,0,1,
1,0,1,0,0,1,0,0,1,1,
1,0,0,1,0,0,0,0,0,1,
1,0,1,0,1,1,1,1,0,1,
1,0,0,0,0,1,0,0,0,1,
1,0,1,0,1,1,0,0,1,1,
1,0,1,1,0,0,0,0,0,1,
1,0,0,0,1,1,0,0,0,1,
1,0,1,0,0,0,1,0,0,1,
1,1,1,0,1,1,1,1,1,1
};*/
int[] _maze = {
1,0,1,1,1,1,1,1,1,1,1,1,
1,0,1,0,0,1,1,1,1,0,1,1,
1,0,0,0,0,0,0,0,0,0,1,1,
1,1,1,0,1,0,1,1,1,1,0,1,
1,0,0,0,1,0,1,0,0,0,0,1,
1,0,1,0,0,1,0,0,1,1,0,1,
1,0,0,1,0,0,0,0,0,0,0,1,
1,0,1,0,1,1,1,1,1,0,0,1,
1,0,0,0,0,1,0,0,0,0,1,1,
1,0,1,0,1,1,1,0,1,0,0,1,
1,0,1,0,0,0,1,0,0,1,0,1,
1,0,1,1,0,1,1,1,0,0,1,1,
1,0,1,0,0,0,1,1,0,1,1,1,
1,1,1,0,1,1,1,1,1,1,1,1
};
public Form1()
{
InitializeComponent();
}
private void Form1_Load(object sender, EventArgs e)
{
_label_obj[0] = new Label();
_label_obj[0].AutoSize = false;
_label_obj[0].Width = 20;
_label_obj[0].Height = 5;
_label_obj[0].Text = "";
_label_obj[0].Font = new Font("Verdana", 12, FontStyle.Bold);
_label_obj[0].ForeColor = Color.Orange;
_label_obj[0].BackColor = Color.Lime;
_label_obj[0].Location = new Point(_label_obj_x, _label_obj_y);
this.Controls.Add(_label_obj[0]);
_label_obj[0].BringToFront();
for (int i = 0; i < _maze.Length; i++)
{
if (i % _row == 0)
{
_label_wall_x = 30;
_label_wall_y += 30;
_label_path_x = 30;
_label_path_y += 30;
}
//產生牆壁
if (_maze[i] == 1)
{
_label_wall[i] = new Label();
_label_wall[i].AutoSize = false;
_label_wall[i].Width = 20;
_label_wall[i].Height = 5;
_label_wall[i].Text = "-";
_label_wall[i].Font = new Font("Verdana", 12, FontStyle.Bold);
//_temperture_txt[i].TextAlign = ContentAlignment.MiddleCenter;
_label_wall[i].ForeColor = Color.Orange;
_label_wall[i].BackColor = Color.Black;
_label_wall[i].Location = new Point(_label_wall_x, _label_wall_y);
this.Controls.Add(_label_wall[i]);
//_label_wall[i].BringToFront();
_label_wall_x += 60;
_label_path_x += 60;
}
//產生通道
else if (_maze[i] == 0)
{
_label_path[i] = new Label();
_label_path[i].AutoSize = false;
_label_path[i].Width = 20;
_label_path[i].Height = 5;
_label_path[i].Text = "";
_label_path[i].Font = new Font("Verdana", 12, FontStyle.Bold);
_label_path[i].ForeColor = Color.Orange;
_label_path[i].BackColor = Color.Orange;
_label_path[i].Location = new Point(_label_path_x, _label_path_y);
this.Controls.Add(_label_path[i]);
//_label_wall[i].BringToFront();
_label_wall_x += 60;
_label_path_x += 60;
}
}
_th = new Thread(walking);
_th.Start();
}
private void walking()
{
//顯示初始座標
updatePath(parameter.status.Running, _label_path[0]);
updatePath(parameter.status.Running, _label_obj[0]);
//定義初始移動位置與方向
_pre_index = index;
r_count = _pre_index += 1;
_pre_index = index;
d_count = _pre_index += _row;
_pre_index = index;
l_count = _pre_index -= 1;
_pre_index = index;
u_count = _pre_index -= _row;
while ((r_count < _maze.Length) && (d_count< _maze.Length) && (l_count<
_maze.Length) && (u_count< _maze.Length))
{
if (_maze[r_count] == 0)
{
_check = true; //有路
if (_check)
{
_st.Push(r_count);//在 stack 加進一格的座標
}
_label_obj_x += 60; //向右走
_pre_index = r_count;
_maze[r_count] = 1; // 走過
updatePath(parameter.status.Running, _label_path[0]);
updatePath(parameter.status.Running, _label_obj[0]);
}
else if (_maze[d_count] == 0)
{
_check = true; //有路
if (_check)
{
_st.Push(d_count);//在 stack 加進一格的座標
}
_label_obj_y += 30; //向下走
_pre_index = d_count;
_maze[d_count] = 1; // 走過
updatePath(parameter.status.Running, _label_path[0]);
updatePath(parameter.status.Running, _label_obj[0]);
}
else if (_maze[l_count] == 0)
{
_check = true; //有路
if(_check)
{
_st.Push(l_count);//在 stack 加進一格的座標
}
_label_obj_x -= 60; //向左走
_pre_index = l_count;
_maze[l_count] = 1; // 走過
updatePath(parameter.status.Running, _label_path[0]);
updatePath(parameter.status.Running, _label_obj[0]);
}
else if (_maze[u_count] == 0)
{
_check = true; //有路
if(_check)
{
_st.Push(u_count);//在 stack 加進一格的座標
}
_label_obj_y -= 30; //向上走
_pre_index = u_count;
_maze[u_count] = 1; // 走過
updatePath(parameter.status.Running, _label_path[0]);
updatePath(parameter.status.Running, _label_obj[0]);
}
else
{
_check = false;
index = (int)_st.Peek();//三面都圍牆時將當前位置設定為牆
_maze[index] = 1; // 走過
_st.Pop();//在 stack 移除後退的格子的座標，退到前一步
index = (int)_st.Peek();
_maze[index] = 0;
if(_maze[index] == 0) //更新移動路徑
{
updatePath(parameter.status.Running, _label_path[0]);
updatePath(parameter.status.Running, _label_obj[0]);
}
}
//更新往四個方向座標
r_count = _pre_index + 1;
d_count = _pre_index + _row;
l_count = _pre_index - 1;
u_count = _pre_index - _row;
Thread.Sleep(50);
}
updatePath(parameter.status.Exit, _label_obj[0]);
MessageBox.Show("Find Exit");
}
private void updatePath(parameter.status current, Control ctl)
{
if (this.InvokeRequired)
{
UpdateUI uu = new UpdateUI(updatePath);
this.Invoke(uu, current, ctl);
}
else
{
if (current == parameter.status.Exit)
{
_label_Exit[0] = new Label();
_label_Exit[0].AutoSize = false;
_label_Exit[0].Width = 20;
_label_Exit[0].Height = 5;
_label_Exit[0].Text = "";
_label_Exit[0].Font = new Font("Verdana", 12, FontStyle.Bold);
_label_Exit[0].ForeColor = Color.Orange;
_label_Exit[0].BackColor = Color.Red;
_label_Exit[0].Location = new Point(_label_obj_x, _label_obj_y);
this.Controls.Add(_label_Exit[0]);
_label_Exit[0].BringToFront();
}
else
{
if(!first)
{
_label_step[_label_step_index] = new Label();
_label_step[_label_step_index].AutoSize = false;
_label_step[_label_step_index].Width = 20;
_label_step[_label_step_index].Height = 5;
_label_step[_label_step_index].Text = "";
_label_step[_label_step_index].Font = new Font("Verdana", 12,
FontStyle.Bold);
_label_step[_label_step_index].ForeColor = Color.Orange;
_label_step[_label_step_index].BackColor = Color.Blue;
_label_step[_label_step_index].Location = new Point(pre_x, pre_y);
this.Controls.Add(_label_step[_label_step_index]);
_label_step[_label_step_index].BringToFront();
}
//ctl.Text = str;
_label_obj[0].Location = new Point(_label_obj_x, _label_obj_y);
this.Controls.Add(_label_obj[0]);
_label_obj[0].BringToFront();
pre_x = _label_obj_x;
pre_y = _label_obj_y;
first = false;
}
}
}
}
}