迷宫问题?

Question

如下:
1101111110
0101010011
1111111010
1101111111
如何判断能从其中一个1(如左上角)到达另一个1(右下角),并且能记录如何走?
上面1表示可以走,我的问题(10*10)中1处较少。  int   maze[10][10]={  
        {0,0,0,0,0,0,0,0,0,0},   
        {0,1,1,0,1,1,1,0,1,0},   
        {0,1,1,0,1,1,1,0,1,0},   
        {0,1,1,1,1,0,0,1,1,0},   
        {0,1,0,0,0,1,1,1,1,0},   
        {0,1,1,1,0,1,1,1,1,0},   
        {0,1,0,1,1,1,0,1,1,0},   
        {0,1,0,0,0,1,0,0,1,0},   
        {0,0,1,1,1,1,1,1,1,0},   
        {0,0,0,0,0,0,0,0,0,0},   
    }; /*定义迷宫*/  
最好给个代码？

Answer 1

using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;namespace MiGong
{
/// <summary>
/// Summary description for Form1.
/// </summary>
public class Form1 : System.Windows.Forms.Form
{
private System.Windows.Forms.ListBox listBox1;
/// <summary>
/// Required designer variable.
/// </summary>
///  public struct Pos
{
public int x;
public int y;
} public struct StackItem
{
public int order;
public int dir;
public Pos curPos;
} private System.ComponentModel.Container components = null; public Form1()
{
//
// Required for Windows Form Designer support
//
InitializeComponent(); //
// TODO: Add any constructor code after InitializeComponent call
//
} /// <summary>
/// Clean up any resources being used.
/// </summary>
protected override void Dispose( bool disposing )
{
if( disposing )
{
if (components != null) 
{
components.Dispose();
}
}
base.Dispose( disposing );
} #region Windows Form Designer generated code
/// <summary>
/// Required method for Designer support - do not modify
/// the contents of this method with the code editor.
/// </summary>
private void InitializeComponent()
{
this.listBox1 = new System.Windows.Forms.ListBox();
this.SuspendLayout();
// 
// listBox1
// 
this.listBox1.ItemHeight = 12;
this.listBox1.Location = new System.Drawing.Point(0, 0);
this.listBox1.Name = "listBox1";
this.listBox1.Size = new System.Drawing.Size(536, 340);
this.listBox1.TabIndex = 0;
// 
// Form1
// 
this.AutoScaleBaseSize = new System.Drawing.Size(5, 15);
this.ClientSize = new System.Drawing.Size(544, 382);
this.Controls.Add(this.listBox1);
this.Name = "Form1";
this.Text = "Form1";
this.Load += new System.EventHandler(this.Form1_Load);
this.ResumeLayout(false); }
#endregion /// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main() 
{
Application.Run(new Form1());
} private void Form1_Load(object sender, System.EventArgs e)
{
MazeStack();
} private void MazeStack()
{
Pos dirPos = new Pos();
dirPos.x = 8;
dirPos.y = 8;
Stack stack = new Stack();
StackItem stackItem = new StackItem();
stackItem.curPos = new Pos();
stackItem.curPos.x = 1;
stackItem.curPos.y = 1; stackItem.order = 0;
stackItem.dir = 0; int [,] arrMaze = new int[10,10]{
 {1,1,1,1,1,1,1,1,1,1},
 {1,0,0,1,0,0,0,1,0,1},
 {1,0,0,1,0,0,0,1,0,1},
 {1,0,0,0,0,1,1,0,0,1},
 {1,0,1,1,1,0,0,0,0,1},
 {1,0,0,0,1,0,0,0,0,1},
 {1,0,1,0,0,0,1,0,0,1},
 {1,0,1,1,1,0,1,1,0,1},
 {1,1,0,0,0,0,0,0,0,1},
 {1,1,1,1,1,1,1,1,1,1}
}; //---------------- Show data in the array --------------------
string str = "";
for(int i = 0; i < arrMaze.GetUpperBound(0); i++)
{
for(int j = 0; j <= arrMaze.GetUpperBound(1); j++)
{
//listBox1.Items.Add(arrMaze[i,j]);
str = str + arrMaze[i,j].ToString();
if (j == arrMaze.GetUpperBound(1))
{
str = str + "\n";
}
}
listBox1.Items.Add(str);
str = "";
}
// --------------- Main body -----------------------------------
do
{
switch(stackItem.dir)
{
case 1:
stackItem.curPos.y = stackItem.curPos.y + 1;
break;
case 2:
stackItem.curPos.x = stackItem.curPos.x + 1;
break;
case 3:
stackItem.curPos.y = stackItem.curPos.y - 1;
break;
case 4:
stackItem.curPos.x = stackItem.curPos.x - 1;
break;
default:
break;
}
if(stackItem.dir == 0)
{
stackItem.dir = 1;
}
if(arrMaze[stackItem.curPos.x,stackItem.curPos.y] == 0)
{
stackItem.order++;
stack.Push(stackItem);
arrMaze[stackItem.curPos.x,stackItem.curPos.y] = 2;
if(stackItem.curPos.x == dirPos.x && stackItem.curPos.y == dirPos.y)
{
break;
}
stackItem.dir = 1;
}
else
{
if(stackItem.dir == 4)
{
if(stack.Count > 0)
{
stack.Pop();
}
if(stack.Count > 0)
{
StackItem stackItemTemp = (StackItem)stack.Pop();
stackItem.dir = stackItemTemp.dir;
stackItem.order = stackItemTemp.order;
stackItem.curPos.x = stackItemTemp.curPos.x;
stackItem.curPos.y = stackItemTemp.curPos.y;
if(stackItem.dir != 4)
{
stackItem.dir++;
}
stack.Push(stackItem);
}
}
else
{
if(arrMaze[stackItem.curPos.x,stackItem.curPos.y] != 0)
{
switch(stackItem.dir)
{
case 1:
stackItem.curPos.y = stackItem.curPos.y - 1;
break;
case 2:
stackItem.curPos.x = stackItem.curPos.x - 1;
break;
case 3:
stackItem.curPos.y = stackItem.curPos.y + 1;
break;
default:
break;
}
stackItem.dir++;
}
}
}
} while(stack.Count > 0); //-----------------------------------------------------------------------------------
// Show Data in the stack
if(stack.Count > 0)
{
while(stack.Count > 0)
{
stackItem = (StackItem)stack.Pop();
listBox1.Items.Add(stackItem.order + "." + "(" + stackItem.curPos.x + "," + stackItem.curPos.y + ")");
}
}
else
{
listBox1.Items.Add("The path don't pass");
}
stack.Clear();
}
}
}