This post comes from the first version of this blog.
Please send me an email if anything needs an update. Thanks!

Z lekkim poślizgiem publikuję analizę kolejnego zadania z konkursu “Potyczki Algorytmiczne” 2011 - 1B “Wieże”. Zadanie nie było trudne, aczkolwiek dosyć ciekawe. Nie udało mi się uzyskać jakiegoś specjalnie optymalnego wyniku, aczkolwiek pomyślnie przeszedłem wszystkie testy i kolejne 10 punktów wylądowało na moim koncie. Warto czasem rozruszać komórki mózgowe, dlatego zapraszam do lektury.

Fotografia: Vittis from Lithuania, CC-BY;

Potyczki Algorytmiczne 2011: Zadanie "Wieże".

Po długich staraniach Bajtek zdołał rozmieścić n wież na szachownicy rozmiaru n×n, tak że żadne dwie wieże nie szachują się. Dla przypomnienia: wieża szachuje wszystkie pola szachownicy znajdujące się w tym samym wierszu lub w tej samej kolumnie co ona.

Niestety, chłopiec przypadkowo potrącił szachownicę, przez co niektóre z wież poprzewracały się i spadły. Czy pomógłbyś mu ustawić te wieże z powrotem? Bajtek prosi, żeby nie ruszać wież, które wciąż stoją na szachownicy.

W pierwszy wierszu standardowego wejścia znajduje się jedna liczba całkowita n (2 <= n <= 1 000), oznaczająca rozmiar szachownicy. Dalej następuje opis ustawienia wież na szachownicy: kolejne n wierszy zawiera po n znaków każdy. Znak ‘.’ oznacza puste pole, a litera ‘W’ reprezentuje pole zajmowane przez wieżę.

Możesz założyć, że na szachownicy stoi w wież, przy czym 1 <= w <= n − 1, oraz że żadna para stojących wież nie szachuje się.

Twój program powinien wypisać na standardowe wyjście reprezentację odpowiednio zapełnionej szachownicy w postaci n wierszy zawierających po n znaków ‘.’ lub ‘W’ każdy. Na planszy powinno występować dokładnie n znaków ‘W’ reprezentujących wieże, przy czym w wież powinno stać dokładnie na takich samych pozycjach jak na wejściu. Żadne dwie wieże nie mogą się szachować. Jeśli istnieje więcej niż jeden sposób dostawienia n − w wież, Twój program może wypisać dowolny z nich.

Dla danych wejściowych:

jednym z poprawnych wyników jest:

....W...
.....W..
..W.....
.......W
W.......
......W.
.W......
...W....

Zobaczmy, jak można rozwiązać to zadanie.

Rozwiązanie.

Pętla rozwiązująca zadanie musiała analizować zawartość pierwszych dwóch n elementów i w momencie, kiedy znalazła “pusty” wiersz i kolumnę, stawiała tam pionek i oznaczała wiersz i kolumnę jako zajętą.

Oto kod, jaki wyprodukowałem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <cstdlib>
#include <cstdio>

int main(void)
	{
	int size = 0, i, j;
	scanf("%d\n", &amp;size);
	bool *rows = (bool *)calloc(size * (size + 2), sizeof(bool));
	char current = 0;
	// read
	for(i = 0; i < size; i++)
		{
		for(j = 0; j < size; j++)
			{
			scanf("%c", &amp;current);
			if('\n' == current)
				{
				j--;
				continue;
				}
			if('W' == current)
				{
				rows[i] = true;
				rows[size + j] = true;
				rows[size * (i + 2) + j] = true;
				}
			}
		}
	// solve
	for(i = 0; i < size; i++)
		{
		for(j = 0; j < size; j++)
			{
			if(rows[size * (i + 2) + j] == true)
				{
				printf("W");
				}
			else if(rows[i] == false &amp;&amp; rows[size + j] == false)
				{
				rows[i] = true;
				rows[size + j] = true;
				// rows[size * (i + 2) + j] = true;
				printf("W");
				}
			else
				{
				printf(".");
				}
			}
		printf("\n");
		}
	return 0;
	}

Optymalizacje.

Uważam, że dosyć istotnym zyskiem jest “skompresowanie” procesu alokowania pamięci do jednego odwołania do calloc() - na początku miałem trzy alokacje dla każdego fragmentu tablicy wynikowej, co jednak zabierało cenne milisekundy.

Ciąg dalszy... stoi pod znakiem zapytania.

Jutro popołudniu postaram się znaleźć chwilę wolnego, żeby spróbować z trzecią rundą, aczkolwiek jest już ona na dosyć wysokim poziomie [nie oszukujmy się, Wieże nie były wcale takie trudne ;]], także nie wiem, czy dam radę. Niektórzy z moich znajomych odpuścili sobie już na drugiej rundzie, ale może coś uda się naskrobać. ;]

Podsumowanie.

Jeśli udało Wam się rozwiązać któreś z zadań z pierwszej albo drugiej rundy - możecie śmiało zamieścić kod w komentarzu używając tagu {code lang=“cpp”}{/code} w nawiasach kwadratowych - tak, tak - trzeba zamienić napisane przeze mnie nawiasy klamrowe na kwadratowe, wtedy kod zostanie ładnie pokolorowany. W razie czego spokojnie - poprawię sam.