witam
Chciałem was poprosić o pomoc, mianowicie napisałem algorytm znajdowania najkrótszej ścieżki i wydaje mi się że powinien on działać ale nie wiem dlaczego nie wykonuje się (zawsze znajduje przeszkodę na punkcie końcowym.
Czy moglibyście przejrzeć mój kod?
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
public static void wypelnij(int x, int y, int liczba, bool[,] scianab, int[,] trasa, int rozmiarX, int rozmiarY)
{
trasa[x, y] = liczba;
if (x - 1 >= 0 && !scianab[x - 1, y] && trasa[x - 1, y] > liczba + 1)
wypelnij(x - 1, y, liczba + 1, scianab, trasa, rozmiarX, rozmiarY);
if (y - 1 >= 0 && !scianab[x, y - 1] && trasa[x, y - 1] > liczba + 1)
wypelnij(x, y - 1, liczba + 1, scianab, trasa, rozmiarX, rozmiarY);
if (x + 1 < rozmiarX && !scianab[x + 1, y] && trasa[x + 1, y] > liczba + 1)
wypelnij(x + 1, y, liczba + 1, scianab, trasa, rozmiarX, rozmiarY);
if (y + 1 < rozmiarY && !scianab[x, y + 1] && trasa[x, y + 1] > liczba + 1)
wypelnij(x, y + 1, liczba + 1, scianab, trasa, rozmiarX, rozmiarY);
}
static void WypiszTablice(int[,] trasa)
{
for (int x = 0; x < trasa.GetLength(0); x++)
{
if (trasa.GetLength(1) > 0)
{
Console.Write(trasa[x, 0]);
}
for (int y = 1; y < trasa.GetLength(1); y++)
{
Console.Write(" "+trasa[x, y]);
}
Console.WriteLine();
}
}
static void Main(string[] args)
{
Console.WriteLine("Wprowadz liczbe kolumn: ");
int a = int.Parse(Console.ReadLine());
Console.WriteLine("Wprowadz liczbe wierszy: ");
int b = int.Parse(Console.ReadLine());
int[,] trasa = new int[a,b];
bool[,] scianab = new bool[a, b];
Random rnd = new Random();
for (int i = 0; i < a; i++)
{
for (int j = 0; j < b; j++)
{
trasa[i, j] = rnd.Next(0, 5) <= 0 ? 5 : 0;
}
}
WypiszTablice(trasa);
for (int i = 0; i < a; i++)
{
for (int j = 0; j < b; j++)
{
if (trasa[i, j] == 0)
{
scianab[i,j] = true;
}
else
{
scianab[i, j] = false;
}
}
}
int[,] trasa2 = new int[a,b];
int rozmiarX = a - 1;
int rozmiarY = b - 1;
int pozycjaX, pozycjaY;
Console.WriteLine("Podaj poczatkowy punkt X: ");
int poczatekX = int.Parse(Console.ReadLine());
Console.WriteLine("Podaj poczatkowy punkt Y: ");
int poczatekY = int.Parse(Console.ReadLine());
Console.WriteLine("Podaj koncowy punkt X: ");
int koniecX = int.Parse(Console.ReadLine());
Console.WriteLine("Podaj poczatkowy punkt Y: ");
int koniecY = int.Parse(Console.ReadLine());
for (int y=0; y <= rozmiarY; y++)
for(int x=0; x <= rozmiarX; x++)
trasa[x,y] = 9999;
wypelnij (koniecX, koniecY, 0, scianab, trasa, rozmiarX, rozmiarY);
pozycjaX = poczatekX;
pozycjaY = poczatekY;
do{
if(scianab[koniecX,koniecY])
{
Console.WriteLine("\nPunkt koncowy jest przeszkoda\n");
goto koniec;
}
for (int y=0; y <= rozmiarY; y++)
{
for (int x=0; x <= rozmiarX; x++)
if (pozycjaX==x && pozycjaY==y)
trasa2[x,y]=3;
else if (koniecX==x && koniecY==y)
trasa2[x,y]=4;
else if (scianab[x,y])
trasa2[x,y]=5;
}
if (pozycjaX > 0 && trasa[pozycjaX,pozycjaY] > trasa[pozycjaX - 1,pozycjaY])
pozycjaX--;
else if (pozycjaY > 0 && trasa[pozycjaX,pozycjaY] > trasa[pozycjaX,pozycjaY - 1])
pozycjaY--;
else if (pozycjaX + 1 < rozmiarX && trasa[pozycjaX,pozycjaY] > trasa[pozycjaX + 1,pozycjaY])
pozycjaX++;
else if (pozycjaY + 1 < rozmiarY && trasa[pozycjaX,pozycjaY] > trasa[pozycjaX,pozycjaY + 1])
pozycjaY++;
} while (pozycjaX != koniecX || pozycjaY != koniecY);
for (int y=0; y <= rozmiarY; y++)
{
for (int x=0; x <= rozmiarX; x++)
if (pozycjaX==x && pozycjaY==y)
Console.WriteLine('X');
else if (koniecX==x && koniecY==y)
Console.WriteLine('Y');
else if (scianab[y,x])
Console.WriteLine('5');
else
Console.WriteLine('0');
Console.WriteLine();
}
Console.WriteLine("\n\n");
Console.WriteLine("Koniec.\n");
for (int y=0; y <= rozmiarY; y++)
{
for (int x=0; x <=rozmiarX; x++)
Console.WriteLine(trasa2[y,x]+"\n");
}
goto koniec2;
koniec:
Console.WriteLine("Brak");
koniec2:
Console.WriteLine("Koniec programu");
Console.ReadLine();
}
}
}