public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
struct zuobiao
{
public int x;
public int y;
public int t;//t=0或1
}
List<zuobiao> A = new List<zuobiao>(); //声明动态结构体数组变量
private void button1_Click(object sender, EventArgs e)//初始化
{
for (int i = 0; i < 9; i++)//赋值
{
for (int j = 0; j < 9; j++)
{
zuobiao zhongjie;
zhongjie.x = i;
zhongjie.y = j;
Random S = new Random();
int S1 = S.Next(1000, 100000);
int S2 = S.Next(100, 1000);
if ((j == 0 && i == 0) || (j == 8 && i == 8))
zhongjie.t=0;
else
{
zhongjie.t = ((S1 * i) % (S2 + j)) % 2;
}
A.Add(zhongjie);
}
}//完成赋值
for (int i = 0; i < 9; i++)//修改迷宫，使其有出路的可能性变大
{
int jishu = 0;
for (int j = 0; j < 9; j++)
{
if (A[i * 9 + j].t == 1)
jishu++;
while (jishu > 6)
{
int t1 = 0;
Random S = new Random();
int S1 = S.Next(i * 9 + 1, i * 9 + j + 1);
if (A[S1].t != 0)
{
zuobiao zhongjie;
zhongjie.x = (S1-S1%9)%9;
zhongjie.y = S1%9;
zhongjie.t = t1;
A.RemoveAt (S1);
A.Insert(S1,zhongjie);
jishu--;
}
}
}
}
label2.Text = "* 0 * * * * * * * * *\n"; //输出边界围墙
for (int j = 0; j < 9; j++)
{
label2 .Text +="* ";//输出边界围墙
for (int k = 0; k < 9; k++)//输出迷宫
{
label2 .Text += A[j * 9 + k].t+" ";
if ((j * 9 + k + 1) % 9 == 0)
{
label2 .Text +="* \n";//输出边界围墙
}
}
}
label2 .Text +="* * * * * * * * * 0 * ";//输出边界围墙
}
private void button2_Click(object sender, EventArgs e)//搜索路径
{
label4.Text = "搜索出的路径:\n";
List<zuobiao> R = new List<zuobiao>();//做容器用
List<zuobiao> Rk = new List<zuobiao>();//盛放新节点的上一节点
List<zuobiao> Rt = new List<zuobiao>();//盛放新节点
zuobiao Rtz;//中介为Rt赋值
Rtz.x = 0;
Rtz.y = 0;
Rtz.t = 0;
Rk.Add(Rtz);//构建初始节点
R.Add(Rtz);//
bool K = false;
while (K == false)//搜索路径
{
Rt.Clear();//必须要保证Rt是空的
for (int i = 0; i < Rk.Count; i++)//扩展下一层
{
int x1, y1;
x1 = Rk[i].x;
y1 = Rk[i].y;//当前最下层节点指代的坐标
int z = x1 * 9 + y1;
if (y1 < 8)
{
if (A[z + 1].t == 0)//当前坐标的右边
{
Rtz.x = x1;
Rtz.y = y1 + 1;
Rtz.t = 0;
int js = 0;
for (int i2 = 0; i2 < R.Count; i2++)//检测是否有重复
{
if (Rtz.x == R[i2].x && Rtz.y == R[i2].y)
{ js++; break; }
}
if (js == 0)
{
Rt.Add(Rtz);//若无重复则赋值
R.Add(Rtz);//这时R也增加了一个元素
}
}
}///////////
if (y1 > 0)
{
if (A[z - 1].t == 0)//当前坐标的左边
{
Rtz.x = x1;
Rtz.y = y1 - 1;
Rtz.t = 0;
int js = 0;
for (int i2 = 0; i2 < R.Count; i2++)//检测是否有重复
{
if (Rtz.x == R[i2].x && Rtz.y == R[i2].y)
{ js++; break; }
}
if (js == 0)
{
Rt.Add(Rtz);//若无重复则赋值
R.Add(Rtz);
}
}
}////////
if (x1 > 0)
{
if (A[z - 9].t == 0)//当前坐标的上边
{
Rtz.x = x1 - 1;
Rtz.y = y1;
Rtz.t = 0;
int js = 0;
for (int i2 = 0; i2 < R.Count; i2++)//检测是否有重复
{
if (Rtz.x == R[i2].x && Rtz.y == R[i2].y)
{ js++; break; }
}
if (js == 0)
{
Rt.Add(Rtz);//若无重复则赋值
R.Add(Rtz);
}
}
}////////
if (x1 < 8)
{
if (A[z + 9].t == 0)//当前坐标的下边
{
Rtz.x = x1 + 1;
Rtz.y = y1;
Rtz.t = 0;
int js = 0;
for (int i2 = 0; i2 < R.Count; i2++)//检测是否有重复
{
if (Rtz.x == R[i2].x && Rtz.y == R[i2].y)
{ js++; break; }
}
if (js == 0)
{
Rt.Add(Rtz);//若无重复则赋值
R.Add(Rtz);
}
}
}///////
}//for循环的括号
if (Rt.Count == 0)//如果没有新节点结束扩展
{
label4.Text += "此迷宫没有可到达出口的路径。";
K = true;
}
else //如果有新节点
{
Rk.Clear();//清空Rk
for (int i = 0; i < Rt.Count; i++)
{
if (Rt[i].x != 8 || Rt[i].y != 8) //判断新扩展的节点是否有出口
{
Rk.Add(Rt[i]);
}
else
{
Rt.Clear();
Rtz.x = 8;
Rtz.y = 8;
Rtz.t = 0;
label4.Text += "\n(0,0)";
Rt.Add(Rtz);
for (int count = R.Count - 1; count > 0; )
{
int h = Math.Abs(R[count].x - Rtz.x);
int l = Math.Abs(R[count].y - Rtz.y);
if ((h == 1 && l == 0) || (h == 0 && l == 1))
{
Rtz.x = R[count].x;
Rtz.y = R[count].y;
Rtz.t = R[count].t;
Rt.Add(Rtz);
}
R.RemoveAt(count);
count--;
}
for (int k = Rt.Count - 1; k >= 0; k--)
{ label4.Text += "\n(" + Rt[k].x + "," + Rt[k].y + ")"; }
label4.Text += "\n你可以在上面的坐标中找出路径。";
K = true;
break;
}
}//for
}//else
}//while的括号
}//but2的括号
}//最外边的括号
}