主題

ZeroJudge - b367: 翻轉世界 解題心得

Not In My Back Yard | 2021-04-10 22:50:00 | 巴幣 0 | 人氣 44

題目連結:


題目大意:
輸入第一列給定一正整數 T (T < 11),代表有 T 筆測試資料。每筆測資第一列給定兩正整數 N 、 M (0 < N 、 M < 11),代表有一個 N 列 M 行的地圖。接著有 N 列輸入,每列給定 M 個整數 r (0 ≦ r < 2 ^ 31),代表地圖的內容。

試問,給定的地圖旋轉 180 度(非水平、垂直翻轉,是指整個版面順時針或逆時針旋轉)後是否與原先相同。如果是則輸出「go forward」;反之,輸出「keep defending」。



範例輸入:
2
3 3
1 1 0
0 1 0
0 1 1
1 5
0 0 1 0 1


範例輸出:
go forward
keep defending


解題思維:
因為不是水平或垂直翻轉,而是 180 度整個旋轉。因此原本地圖最左上的數字會跑到最右下、最右上會跑到最左下等等。更正式地說,第 i 列第 j 行(索引值都從 0 開始數)的數字旋轉 180 度後會跑到
第 N - i - 1 列第 M - j - 1 行
的位置。

因此,我們可以直接掃過給定的二維陣列(假設叫做 A)的每個位置 A[i][j],將其與 A[N - i - 1][M - j - 1] 相比。如果對於任意 (i, j) 數對都是兩者皆相同,則代表著旋轉前與旋轉後的陣列 A 之內容皆相同。因此輸出「go forward」;反之,輸出「keep defending」。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作