using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int[,] i = {
{0,0,1,0},
{1,0,0,0},
{1,0,0,0}
};
Maze m = new Maze(getdata(i));
foreach (var item in m.Travel())
{
Console.WriteLine(item);
}
}
static bool[,] getdata(int[,] d)
{
int h = d.GetLength(0);
int w = d.GetLength(1);
bool[,] info = new bool[h, w];
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
info[i, j] = (d[i, j] == 0);
}
}
return info;
}
}
enum Direction
{
Up, Down, Left, Right
}
class Point : IEquatable<Point>
{
public int X { get; private set; }
public int Y { get; private set; }
public Point(int x, int y)
{
X = x;
Y = y;
}
public override string ToString()
{
return string.Format("[{1},{0}]", X, Y);
}
#region IEquatable<Position> Members
public bool Equals(Point other)
{
return this.X == other.X && this.Y == other.Y;
}
#endregion
}
class MazeItem
{
public Point Point { get; private set; }
public bool Visitable { get; private set; }
public MazeItem(int x, int y, bool canVisit)
{
Point = new Point(x, y);
Visitable = canVisit;
}
public override string ToString()
{
return Point + "-" + Visitable;
}
}
class Maze
{
public int Width { get; private set; }
public int Height { get; private set; }
MazeItem[,] data;
MazeItem emptyItem = new MazeItem(-1, -1, false);
public Maze(bool[,] array)
{
Height = array.GetLength(0);
Width = array.GetLength(1);
data = new MazeItem[Height, Width];
for (int w = 0; w < Width; w++)
{
for (int h = 0; h < Height; h++)
{
data[h, w] = new MazeItem(w, h, array[h, w]);
}
}
}
public IEnumerable<MazeItem> Travel()
{
var path = new List<MazeItem>();
TryTravel(new Point(0, 0), path);
return path;
}
MazeItem GetItem(Point point)
{
if (point.X >= Width || point.X < 0)
return emptyItem;
if (point.Y >= Height || point.Y < 0)
return emptyItem;
return data[point.Y, point.X];
}
IEnumerable<Direction> Directions()
{
yield return Direction.Up;
yield return Direction.Down;
yield return Direction.Left;
yield return Direction.Right;
}
Point GetNextPoint(Point current, Direction direction)
{
switch (direction)
{
case Direction.Up:
return new Point(current.X, current.Y - 1);
case Direction.Down:
return new Point(current.X, current.Y + 1);
case Direction.Left:
return new Point(current.X - 1, current.Y);
case Direction.Right:
return new Point(current.X + 1, current.Y);
default:
return current;
}
}
//尝试将节点从pos的位置移动到终点，将新增的访问路径添加到visited中，如果无法访问则不能修改visited内容。
//返回值表示是否可以从pos移动到终点
bool TryTravel(Point pos, List<MazeItem> visited)
{
int len = visited.Count;
visited.Add(GetItem(pos));
if (pos.X == (Width - 1) && pos.Y == (Height - 1))
{
return true;
}
foreach (var direction in Directions())
{
Console.WriteLine(direction);
Point npoint = GetNextPoint(pos, direction);
MazeItem nItem = GetItem(npoint);
if (!nItem.Visitable) //新的节点是否可以访问
continue;
if (visited.Contains(nItem)) //已经访问过的路径不能再访问
continue;
Console.WriteLine(pos + "-" + npoint);
foreach (var item in visited)
{
Console.Write(item.Point + "-");
}
Console.WriteLine();
Console.ReadLine();
if (TryTravel(npoint, visited))
{
return true;
}
else
{
//无法访问，需要把新插入的访问路径去掉
visited.RemoveRange(len, visited.Count - len - 1);
}
}
//无法访问，需要把已经放入访问路径的pos去掉
visited.RemoveAt(len);
return false;
}
}
}
（本文已被浏览 次） | | |
相关评论
