Palīdzība ar vienu algoritmu.

Vieta, kur parunāt par to, kas nav atsevišķi izdalīts augstāk
Post Reply
Message
Author
User avatar
kristapuciitis
Posts: 163
Joined: 03 Jun 2011, 14:22

Palīdzība ar vienu algoritmu.

#1 Post by kristapuciitis » 05 Nov 2012, 21:45

Sveiki! Man uzradās problēma atrisināt šo uzdevumu. Atrisināju šī uzdevuma vieglāko variantu, bet nevaru izdomāt algoritmu, lai atrisinātu pilno uzdevumu. Rekur kods vieglākajam variantam, risināju ar dinamisko programmēšanu, bet šķiet, ka pilnajam uzdevumam nederēs šāds līdzīgs piegājiens. Kādam ir kādas idejas?

Code: Select all

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	freopen("lielkva.dat", "r", stdin);
	freopen("lielkva.rez", "w", stdout);

	string lastRow;
	string currentRow;
	vector<int> lastCount;
	vector<int> currentCount;
	int n, max = 1;

	cin >> n;
	cin >> lastRow;
	for (int i = 0; i < n; i++)
	{
		lastCount.push_back(1);
		currentCount.push_back(1);
	}

	for (int i = 1; i < n; i++)
	{
		cin >> currentRow;
		currentCount[0] = 1;

		for (int j = 1; j < n; j++)
		{
			if (currentRow[j] == currentRow[j-1] &&
				currentRow[j] == lastRow[j] &&
				currentRow[j] == lastRow[j-1])
			{
				currentCount[j] = min(currentCount[j-1], min(lastCount[j], lastCount[j-1])) + 1;
			}
			else
			{
				currentCount[j] = 1;
			}

			if (currentCount[j] > max)
			{
				max = currentCount[j];
			}
		}

		lastCount = currentCount;
		lastRow = currentRow;
	}
	
	cout << max;

	return 0;
};
Gooby pls

Post Reply

Return to “Programmēšana / Programming”