Prośba o pomoc z macierzami

[yula]

Rozpatrujemy kwadratowe macierze o elementach będących pojedynczymi literami alfabetu
(‘a’… ‘z’, ‘A’… ‘Z’). Definiujemy następujący zestaw operacji (macierz wejściowa to A, a wynikowa – B, obie o rozmiarach nn):
 T – transpozycja względem głównej przekątnej: Bj, i = Ai, j
 D – transpozycja względem drugiej przekątnej: Bn-j+1, n-i+1 = Ai, j
 H – odbicie poziome (względem osi pionowej): Bi, n-j+1 = Ai, j
 V – odbicie pionowe (względem osi poziomej): Bn-i+1, j = Ai, j
 A – obrót w prawo o 90°: Bj, n-i+1 = Ai, j
 B – obrót w prawo o 180°
 C – obrót w prawo o 270°
 X – obrót w lewo o 90°: Bn-j+1, i = Ai, j
 Y – obrót w lewo o 180°
 Z – obrót w lewo o 270°
dla i, j {1, 2,…, n}
Zadanie
Napisz program, który dla danej macierzy wyjściowej obliczy rezultat złożenia nie więcej niż
100 000 powyższych operacji.
Wejście
Standardowe wejście zawiera zestaw testów. Pierwszy wiersz wejścia zawiera jedną liczbę D
(0 < D < 20) określającą liczbę testów. Kolejne wiersze zawierają dane związane z testami. W
pierwszym wierszu każdego testu występuje zawsze jedna liczba n określająca rozmiary macierzy (liczba wierszy = liczba kolumn = n; 0 < n ≤ 300; wartości n w kolejnych testach mogą
być różne). Kolejne n wierszy zawiera po n liter (bez odstępów) będących elementami wejściowej macierzy. Ostatni wiersz testu zawiera ciąg operacji do wykonania zapisany przy pomocy
ciągu znaków podanych przy ich definicjach powyżej. Ciąg ten jest zakończony znakiem ’&’
(bez apostrofów). Operacje powinny być wykonane w kolejności od lewej do prawej.
Wyjście
Każdemu testowi powinna odpowiadać w standardowym wyjściu macierz uzyskana w wyniku
wykonania ciągu zadanych operacji. Format wyprowadzonej macierzy powinien być taki sam,
jak w danych wejściowych, tzn. n wierszy po n znaków (bez spacji).

moje rozwiązanie https://ideone.com/gjH43h , chyba poprawne jak coś nie zepsułam, ale dużo za wolne dla większych danych. Jak można przyśpieszyć?

[quenthui]

Jeśli dobrze rozumiem, to dla całej sekwencji wykonujesz kolejne operacje na całej macierzy, co daje złożoność O(NxNxm).

Tak myślę, czy nie będzie szybciej wziąć każdy element oddzielnie i na nim wykonywać kolejne operacje. Dzięki temu unikasz skakania po tablicy, jedynie modyfikując indeksy. Nie zmienia to złożoności, ale może się szybciej wykonywać.

Powyższe podejście prowadzi do kolejnego rozwiązania: Weź skrajne elementy: (0, 0), (0, N-1), (N-1, 0), (N-1, N-1) i dla nich przeprowadź wszystkie operacje. Zobacz, gdzie wylądują w końcowej macierzy.
Zastanów się teraz, jakie są możliwe końcowe pozycje.
Znając położenie czterech narożników, jesteś w stanie wywnioskować układ całej wynikowej macierzy (położenie elementów względem siebie nie zmienia się. Może powstać co najwyżej lustrzane odbicie).
W ten sposób schodzisz do rozwiązania O(m + NxN), czyli O(m).

Co o tym myślisz? Swoją drogą bardzo fajne zadanie

[yula]

Tak myślę, czy nie będzie szybciej wziąć każdy element oddzielnie i na nim wykonywać kolejne operacje. Dzięki temu unikasz skakania po tablicy, jedynie modyfikując indeksy. Nie zmienia to złożoności, ale może się szybciej wykonywać.

eeee… nie bardzo widzę jak można operować tylko na wierzchołkach… Jak widać w kodzie myślałam o sumowaniu obrotów i zmniejszaniu ilości operacji bo poza obrotami każda razy dwa wraca do początku

[quenthui]

nie bardzo widzę jak można operować tylko na wierzchołkach

Zaczynasz od wierzchołka (0, 0) i na nim wykonujesz kolejne operacje. Transpozycja względem głównej daje wierzchołek (N-1, N-1). Potem kolejny obrót o 90 w lewo to (0, N-1) itd. Po wszystkich operacjach masz nową pozycje elementu (0, 0).
Potem bierzesz element (0, 1) i powtarzasz całą procedurę.
Złożoność ta sama, ale przy maksymalnym rozmiarze macierzy, może mieć znaczenie.

[quenthui]

Ale jak się zastanowisz, co się dzieje z elementami podczas tych obrotów, to okaże się, że potrzebujesz sprawdzić tylko dwa (nawet nie 4, jak pisałem wcześniej) elementy, które powiedzą ci, jaka jest orientacja końcowej macierzy. Położenie reszty elementów można już z tego wywnioskować.
Tylko jedna uwaga, wybrane elementy powinny być z tego samego wiersza, albo tej samej kolumny.

[yula]

Obroty to prosto, ale reszta jednak miesza środek , i jak po wierzchołkach odzyskać całą macierz?

[m_labanowicz]

Jakby tak rozpatrzyc tylko macierz 4x4, ktora ma wydzielone grupy, ktore mozna “zamapowac” do tej oryginalnej:

| a b c d |
| e f g h |
| i j k l |
| m n o p |

Wtedy może po tych wszystkich operacjach bedzie mozna stwierdzic, gdzie i w jaki sposob dana grupa "wylądowała’.

[yula]

Tam są maksymalne rozmiary 300x300… Głowa zaraz wybuchnie…

[quenthui]

Obroty to prosto, ale reszta jednak miesza środek

Własnie, że nie miesza. Wyobraź sobie, że macierz to prześwitująca kartka papieru z obrazkiem. Jakbyś go nie obracała i przekładała na drugą stronę, obrazek pozostanie ten sam (co najwyżej jego lustrzane odbicie).

i jak po wierzchołkach odzyskać całą macierz?

Wyobraź sobie, że na obrazku masz strzałkę (skierowaną do dołu) w lewym górnym rogu, która wskazuje kierunek wypisywania wierszy.
Po wszystkich transformacjach, strzałka może znajdować się w jednym z 4 rogów i wskazywać kierunek poziomy lub pionowy. I to będzie kierunek rysowania macierzy. Masz tylko 8 przypadków, które musisz na koniec sprawdzić.

Strzałką może być to, co wcześniej pisałem. Bierzesz elementy: (0,0) i (1,0) - lewy górny róg i element pod nim. Na obu elementach wykonujesz wszystkie przekształcenia, sprawdzasz ich końcowe położenie i względem nich rysujesz całą macierz.

Przyjrzyj się wynikowym macierzom, które generuje Twoje rozwiązanie.

[narbej]

Operacje powinny być wykonane w kolejności od lewej do prawej.

Powinny? Ale nie muszą?
Jeżeli tak, to może posortować je, pozsumować, skrócić itd…

[yula]

tu raczej oznacza że muszą (wynik ma być taki), chyba że czegoś nie zauważyłam, skracanie co wymyśliłam to wyżej pisałam, (sumowanie obrotów i podwójne inne)

[narbej]

Może się mylę, jestem w pracy… Czy obrót, transpozycja, obrót, to pewnie nie to samo co obrót, obrót, transpozycja?

Ps
Ale pomysł z “wzorcową” macierzą 4x4 wydaje mi się sensowny.

Ps 2
A to zadanie jest na jakimś portalu?

[pawoj20]

obrót, odbicie lustrzane poziome, obrót
nie jest tym samym co
obrót, obrót, odbicie lustrzane poziome.
Gdy obroty są jeden po drugim można je sumowac.

[yula]

Niestety nie na portalu, przynajmniej ja mam nie z portalu. Chyba dzięki odpowiedziom mam pomysł jak zrobić . Jutro spróbuję doprowadzić do ładu, bo dziś gdzieś sie machnęłam, i potestuje czy dobrze myślę

[hipcia]

Idąc krok dalej nie ma potrzeby modyfikowania ani jednego elementu macierzy. Wszystkie osiem końcowych pozycji można utworzyć przez zamianę zakresów pętli, lub samych indeksów:

#include <iostream>
#include <numeric>
#include <string>

struct Matrix {
	int n = 3;
	std::string data;
public:
	Matrix() :data(n * n, ' ') {
		std::iota(data.begin(), data.end(), 'a');
	}

	void show(int k) const {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				int idx = access(i, j, k);
				std::cout << data[idx] << " ";
			}
			std::cout << "\n";
		}
		std::cout << std::string(5, '-') << "\n";
	}

protected:
	int access(int i, int j, int k) const {     
		// A[i][j] - origin
		// A[j][i] - T
		// A[i][n - j - 1] - H
		// A[j][n - i - 1] - C, X
		// A[n - i - 1][j] - V
		// A[n - j - 1][i] - A, Z
		// A[n - j - 1][n - i - 1] - D
		// A[n - i - 1][n - j - 1] - B, Y

		bool flip_x  = (k >> 0) & 1;
		bool flip_y  = (k >> 1) & 1;
		bool flip_xy = (k >> 2) & 1;

		if (flip_x)
			i = n - i - 1;
		if (flip_y)
			j = n - j - 1;
		if (flip_xy)
			std::swap(i, j);
		return i * n + j;
	}
};

int main() {
	Matrix m;
	for (int i = 0; i < 8; ++i) {
		m.show(i);
	}
}

Każda zamiana może być nanoszona na kolejną np:

...
	void vertical_reflection() {
		flip_x = !flip_x;
	}

	void horizontal_reflection() {
		flip_y = !flip_y;
	}

    void transpose_first_diagonal() {
		flip_xy = !flip_xy;
		std::swap(flip_x, flip_y);
	}
...

switch (move) {
case 'A': rotate90(); break;
case 'C': reverse_rotate90(); break;
case 'X': reverse_rotate90(); break;
case 'Z': rotate90(); break;

case 'Y':
case 'B': rotate180(); break;

case 'T': transpose_first_diagonal(); break;
case 'D': transpose_second_diagonal(); break;
case 'H': horizontal_reflection(); break;
case 'V': vertical_reflection(); break;
}
...

[yula]

pomyślę nad tym później, na razie mam alergię na macierze Moja działająca wersja ze śmieciami https://ideone.com/lZ3XyO

[yula]

dzięki wszystkim za pomoc

[korkirw]

No, trochę atramentu na to poszło… : Chyba sobie kiedyś spokojnie usiądę i przeanalizuję Twój kod

[yula]

Ja już widzę że można sporo skrócić, sporo nadmiaru, ale w tej chwili nie mam siły na to patrzeć A i tam analize robi krok po kroku przekształcenia macierzy, analiza - próbuję skracać ale afekty słabe. No i poszczególne funkcje przekształcania, też parę nadmiarowych i nie wyrzuconych…