Задача состоит в том, что нужно найти путь в двумерном массиве (от точки А до точки Б). Как это сделать на С#?
3 ответа
Возможно не самая быстрая реализация, зато с описанием и картинками, тебе же сейчас главное понять сам принцип работы, ведь так? Потому как для реальных проектов волновой алгоритм в чистом виде - не самое лучшее решение.
Реализовано с использованием ООП. Описание алгоритма взято с wiki.
Код:
using System;
using System.Linq;
using System.Collections.Generic;
namespace Finder
{
class Program
{
static void Main(string[] args)
{
const int heigth = 10;
const int width = 18;
int[,] my = new int[heigth, width];
for (int i = 0; i < heigth; i++)
{
for (int j = 0; j < width; j++)
{
var rand = new Random(unchecked((int)DateTime.Now.Millisecond));
if (rand.Next(100) > 70)
my[i, j] = (int)Figures.Barrier;
else
my[i, j] = (int)Figures.EmptySpace;
}
}
var random = new Random(unchecked((int)DateTime.Now.Millisecond));
my[random.Next(heigth), random.Next(width)] = (int)Figures.StartPosition;
my[random.Next(heigth), random.Next(width)] = (int)Figures.Destination;
Print(my);
LeeAlgorithm li = new LeeAlgorithm(my);
Console.WriteLine(li.PathFound);
if (li.PathFound)
{
foreach (var item in li.Path)
{
if (item == li.Path.Last())
my[item.Item1, item.Item2] = (int)Figures.StartPosition;
else if (item == li.Path.First())
my[item.Item1, item.Item2] = (int)Figures.Destination;
else
my[item.Item1, item.Item2] = (int)Figures.Path;
}
Print(li.ArrayGraph);
Console.WriteLine("Длина " + li.LengthPath);
}
else
Console.WriteLine("Путь не найден");
Console.ReadLine();
}
private static void Print(int[,] array)
{
Console.WriteLine("***");
string msg = string.Empty;
int x = array.GetLength(0);
int y = array.GetLength(1);
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
{
switch (array[i, j])
{
case (int)Figures.Path: msg = string.Format("{0,3}", "+"); Console.ForegroundColor = ConsoleColor.Yellow; break;
case (int)Figures.StartPosition: msg = string.Format("{0,3}", "s"); Console.ForegroundColor = ConsoleColor.Green; break;
case (int)Figures.Destination: msg = string.Format("{0,3}", "d"); Console.ForegroundColor = ConsoleColor.Red; break;
case (int)Figures.EmptySpace: msg = string.Format("{0,3}", "'"); Console.ForegroundColor = ConsoleColor.DarkBlue; break;
case (int)Figures.Barrier: msg = string.Format("{0,3}", "*"); Console.ForegroundColor = ConsoleColor.Blue; break;
case 1:
case 2:
case 3:
case 4:
case 5:
case 6:
case 7:
case 8:
case 9:
case 10:
case 11:
case 12:
case 13:
case 14:
case 15:
case 16:
case 17:
case 18:
case 19:
case 20:
msg = string.Format("{0,3}", array[i, j]); Console.ForegroundColor = ConsoleColor.DarkGray; break;
default:
break;
}
Console.Write(msg);
Console.ResetColor();
}
Console.WriteLine();
}
Console.WriteLine(msg);
}
}
public class LeeAlgorithm
{
public int[,] ArrayGraph { get; private set; }
/// <summary>
/// Начало пути с конца списка
/// </summary>
public List<Tuple<int, int>> Path { get; private set; }
public int Width { get; private set; }
public int Heidth { get; private set; }
public bool PathFound { get; private set; }
public int LengthPath { get { return Path.Count; } }
private int _step;
private bool _finishingCellMarked;
private int _finishPointI;
private int _finishPointJ;
/// <summary>
/// Инициализирует новый экземпляр объекта с полем и указанием начальной точки
/// </summary>
public LeeAlgorithm(int startX, int startY, int[,] array)
{
ArrayGraph = array;
Width = ArrayGraph.GetLength(0);
Heidth = ArrayGraph.GetLength(1);
SetStarCell(startX, startY);
PathFound = PathSearch();
}
/// <summary>
/// Инициализирует новый экземпляр объекта с полем. Начальной точка установлена в массиве
/// </summary>
public LeeAlgorithm(int[,] array)
{
ArrayGraph = array;
Width = ArrayGraph.GetLength(0);
Heidth = ArrayGraph.GetLength(1);
int startX;
int startY;
FindStartCell(out startX, out startY);
SetStarCell(startX, startY);
PathFound = PathSearch();
}
private void FindStartCell(out int startX, out int startY)
{
int w = Width;
int h = Heidth;
for (int i = 0; i < w; i++)
{
for (int j = 0; j < h; j++)
{
if (ArrayGraph[i, j] == (int)Figures.StartPosition)
{
startX = i;
startY = j;
return;
}
}
}
throw new AggregateException("Нет начальной точки");
}
private void SetStarCell(int startX, int startY)
{
if (startX > this.ArrayGraph.GetLength(0) || startX < 0)
throw new ArgumentException("Неправильная координата x");
if (startY > this.ArrayGraph.GetLength(1) || startY < 0)
throw new ArgumentException("Неправильная координата x");
//Пометить стартовую ячейку d:= 0
_step = 0;
ArrayGraph[startX, startY] = _step;
}
private bool PathSearch()
{
if (WavePropagation())
if (RestorePath())
return true;
return false;
}
// Есть. Ортогональный путь
// Todo. Ортогонально-диагональный путь
/// <summary>
/// Распространение волны
/// </summary>
/// <returns></returns>
private bool WavePropagation()
{
//ЦИКЛ
// ДЛЯ каждой ячейки loc, помеченной числом d
// пометить все соседние свободные непомеченные ячейки числом d + 1
// КЦ
// d := d + 1
//ПОКА(финишная ячейка не помечена) И(есть возможность распространения волны)
int w = Width;
int h = Heidth;
bool finished = false;
do
{
for (int i = 0; i < w; i++)
{
for (int j = 0; j < h; j++)
{
if (ArrayGraph[i, j] == _step)
{
// Пометить все соседние свободные непомеченные ячейки числом d + 1
if (i != w - 1)
if (ArrayGraph[i + 1, j] == (int)Figures.EmptySpace) ArrayGraph[i + 1, j] = _step + 1;
if (j != h - 1)
if (ArrayGraph[i, j + 1] == (int)Figures.EmptySpace) ArrayGraph[i, j + 1] = _step + 1;
if (i != 0)
if (ArrayGraph[i - 1, j] == (int)Figures.EmptySpace) ArrayGraph[i - 1, j] = _step + 1;
if (j != 0)
if (ArrayGraph[i, j - 1] == (int)Figures.EmptySpace) ArrayGraph[i, j - 1] = _step + 1;
// Путь до финиша проложен
if (i < w - 1)
if (ArrayGraph[i + 1, j] == (int)Figures.Destination)
{
_finishPointI = i + 1;
_finishPointJ = j;
finished = true;
}
if (j < h - 1)
if (ArrayGraph[i, j + 1] == (int)Figures.Destination)
{
_finishPointI = i;
_finishPointJ = j + 1;
finished = true;
}
if (i > 0)
if (ArrayGraph[i - 1, j] == (int)Figures.Destination)
{
_finishPointI = i - 1;
_finishPointJ = j;
finished = true;
}
if (j > 0)
if (ArrayGraph[i, j - 1] == (int)Figures.Destination)
{
_finishPointI = i;
_finishPointJ = j - 1;
finished = true;
}
}
}
}
_step++;
//ПОКА(финишная ячейка не помечена) И(есть возможность распространения волны)
} while (!finished && _step < w * h);
_finishingCellMarked = finished;
return finished;
}
/// <summary>
/// Восстановление пути
/// </summary>
/// <returns></returns>
private bool RestorePath()
{
// ЕСЛИ финишная ячейка помечена
// ТО
// перейти в финишную ячейку
// ЦИКЛ
// выбрать среди соседних ячейку, помеченную числом на 1 меньше числа в текущей ячейке
// перейти в выбранную ячейку и добавить её к пути
// ПОКА текущая ячейка — не стартовая
// ВОЗВРАТ путь найден
// ИНАЧЕ
// ВОЗВРАТ путь не найден
if (!_finishingCellMarked)
return false;
int w = Width;
int h = Heidth;
int i = _finishPointI;
int j = _finishPointJ;
Path = new List<Tuple<int, int>>();
AddToPath(i, j);
do
{
if (i < w - 1)
if (ArrayGraph[i + 1, j] == _step - 1)
{
AddToPath(++i, j);
}
if (j < h - 1)
if (ArrayGraph[i, j + 1] == _step - 1)
{
AddToPath(i, ++j);
}
if (i > 0)
if (ArrayGraph[i - 1, j] == _step - 1)
{
AddToPath(--i, j);
}
if (j > 0)
if (ArrayGraph[i, j - 1] == _step - 1)
{
AddToPath(i, --j);
}
_step--;
} while (_step != 0);
return true;
}
private void AddToPath(int x, int y)
{
Path.Add(new Tuple<int, int>(x, y));
}
}
public enum Figures
{
StartPosition = 0,
EmptySpace = -1,
Destination = -2,
Path = -3,
Barrier = -4
}
}