Quadratische Matrix um 90° drehen

[KäseSahne]

Hallo Forum,

leider muss ich euch mal wieder mit einer Frage belästigen...
Ich soll eine Methode schreiben, der ich als Parameter ein 2D-Array (quadratisch) übergebe. Diese soll das Array um 90° drehen und wieder zurück geben. Der Witz an der Aufgabe ist jedoch, dass kein weiteres Hilfsarray erzeugt werden darf, sondern ausschließlich auf dem originalen Array gearbeitet werden soll.

Aus:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

soll
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4

werden.
Ich sitze jetzt schon einige Zeit an der Aufgabe und kann keinen Ansatz finden. Wäre nett, wenn mir jemand auf die Sprünge helfen könnte.

Vielen Dank im Voraus!

 

[Gast2]

Du musst immer zwei Werte tauschen. Mals dir auf nen Blatt Papier auf und schau dir an welche Werte getauscht werden müssen, da solltest du dann nen schönes Muster erkennen.

 

[KäseSahne]

Hallo EikeB,

danke für deine Antwort. Das paarweise Tauschen ist mir klar. Jedoch muss ich doch in meinem Beispiel immer vier Werte in einem "Zug" tauschen, oder? Soll heißen, wenn ich bei der 1 anfange, muss ich mit der 4, 16, 13 weitermachen, da mir sonst ein Wert verloren geht. Ist der Gedankengang richtig?
Hier mal die Positionsangaben der ersten beiden Schritte:
1.Schritt:
[0,0] tauschen mit [0,3]
[0,3] tauschen mit [3,3]
[3,3] tauschen mit [3,0]
[3,0] tauschen mit [0,0]

2.Schritt:
[0,1] tauschen mit [1,3]
[1,3] tauschen mit [3,2]
[3,2] tauschen mit [2,0]
[2,0] tauschen mit [0,1]

(getauscht werden hier immer die alten Anfangswerte)

Leider finde ich hier den roten Faden nicht, um rechnerisch auf die Folgepositionen zu schließen.

 

[Marco13]

Vertauscht wird da doch gar nichts....!?

Bei einer Matrix der Größe rs*cs wandert der Eintrag (r,c) an die Position (c,rs-1-r). Der Eintrag, der dadurch "verdrängt" wird, wandert an eine Zielposition, die genauso berechnet wird. Das ganze 4 mal. So kann man jeden einzelnen Eintrag "rumschieben", außer natürlich denen, die schonmal "rumgeschoben" oder "verdrängt" wurden.

Fand' das jetzt auch mal ganz spannend...

Spoiler: Ich heiße nicht 'KäseSahne' oder habe keinen Bock auf Hausaufgaben

class RotateMatrix
{
    public static void main(String args[])
    {
        int w = 5;
        int h = 5;
        int m[][] = new int[h][w];
        int n = 1;
        for (int i=0; i<m.length; i++)
        {
            for (int j=0; j<m[i].length; j++)
            {
                m[i][j] = n++;
            }
        }

        System.out.println("Input");
        print(m);

        rotate(m);

        System.out.println("Output");
        print(m);

    }

    private static void print(int m[][])
    {
        for (int i=0; i<m.length; i++)
        {
            for (int j=0; j<m[i].length; j++)
            {
                System.out.printf("%3d", m[i][j]);
            }
            System.out.println();
        }
    }


    public static void rotate(int m[][])
    {
        int rs = m.length;
        int cs = m[0].length;

        for (int k=0; k<rs/2; k++)
        {
            //System.out.println("For k="+k);
            for (int j=k; j<cs-1-k; j++)
            {
                //System.out.println("For j="+j);
                int r0 = k;
                int c0 = j;
                int current = m[r0][c0];
                for (int i=0; i<4; i++)
                {
                    int c1 = rs-1-r0;
                    int r1 = c0;
                    int next = m[r1][c1];
                    //System.out.println("From "+r0+" "+c0+" to "+r1+" "+c1);
                    //System.out.println("Move "+current+" to "+next);
                    m[r1][c1] = current;
                    current = next;
                    r0 = r1;
                    c0 = c1;
                }
            }
        }

    }

}

 

[KäseSahne]

Vielen Dank für die Hilfe:toll:. "Tauschen" war nicht die richtige Wortwahl, ich weiß
Aber auf diese Formel wäre ich so schnell mit Sicherheit nicht gekommen.

Gruß

 

[Landei]

Im Prinzip kann man die Drehung über die Formeln zur 2D-Rotation um den Ursprung ableiten:

x' = x cos f - y sin f
y' = y cos f + x sin f

f ist der Drehwinkel, bei dir also +-90° (für Java also +-Math.PI / 2). Das Problem ist, dass dein "Ursprung" für die Rotation nicht in der Ecke, sondern in der Mitte der Matrix liegt, es müssen also deine Koordinaten erst hin- und dann wieder zurückverschoben werden. Wird hier erklärt: 2D Rotation

Das alles ist natürlich Overkill für eine 90°-Drehung mit ganzzahligen Koordinaten, aber es kann nicht schaden zu wissen, wie die Vertauschungen eigentlich zustande kommen.