Programozás

[Cpt Balu]

Originally Posted by Kutyuleee

egy forráskódot nekem is küldenél??? elsőre én is hasonló algoritmusban gondolkodtam csak nem volt időm még foglalkozni vele.

Még annyi a kérdés, hogy az eredeti feladatban használható-e rekurzió vagy nem?

Mivel a megoldás maga egyszerűbb, mint a magyarázkodás :P ezért itt postolom az algoritmust C# kódját:

public static class Searcher
{
	public static int[,] Table;
	static int Width, Height;<-- Tábla méretei
	public static void SetTable(int W, int H)
	{Adott méretű tábla generálása}
	public static void Fill(double p)
	{Feltöltés random szám segítségével, Rand<p?1:0 alapján}
	public static void Search(ref int X, ref int Y, ref int W, ref int H)
	{A kereső függvényünk}
}

Eddig a bevezetés, hogy hogy is néz ki a tábla, tehát int tömb, 1 és 0, ebben fogunk keresgélni.
A következő függvény adja a megoldást, az eredmények
X,Y,W,H változókba kerülnek (híváskor W értéke -1, a többi lényegtelen), amit a hívás helyén tudunk felhasználni:

public static void Search(ref int X, ref int Y, ref int W, ref int H)
{
	int[,] Dists = new int[Width, Height];
	int[] Stack1 = new int[Width];
	int Stack1P = 0;
	for (int i = Width - 1; i > -1; i--)
	{
		for (int j = Height - 1; j > -1; j--)
			if (Table[i, j] == 1)
				Dists[i, j] = (i == Width - 1 || Table[i + 1, j] == 0) ? 1 : Dists[i + 1, j] + 1;
			else
				Dists[i, j] = 0;
		Stack1[i] = 0;
	}
	for (int i = 0; i < Width; i++)
		if (W == -1 || (Width - i) * Height > W * H)
		{
			int C1 = 0;
			int CF = 0;
			while (C1 <= Height)
			{
				int N = C1 == Height ? 0 : Dists[i, C1];
				if (N == 0)
					CF = C1 + 1;
				while (N != Stack1P)
				{
					if (N > Stack1P)
					{
						Stack1[Stack1P] = C1;
						Stack1P++;
					}
					else if (N < Stack1P)
					{
						Stack1P--;
						int newh = C1 - Stack1[Stack1P];
						int neww = Stack1P + 1;
						if (neww * newh > W * H)
						{
							W = neww;
							H = newh;
							X = i;
							Y = Stack1[Stack1P];
						}
						Stack1[Stack1P] = -1;
						if (Stack1[Stack1P] == CF)
							Stack1P = N;
					}
				}
				C1++;
			}
		}
}

Nem túl hosszú kód, de annál bonyolultabb értelmezni, kíváncsi vagyok ki jön rá mit is csinál pontosan Lehet ötletelgetni!
Segítség: az első for ciklus (for (int i = Width - 1; i > -1; i--)) törzsének végéig az oldalon leírtak szerint működik.