APCS2017-0304-3 數字龍捲風 (zerojudge c292)
給定一個 N*N 的二維陣列,其中 N 是奇數,我們可以從正中間的位置開始順時 針旋轉的方式走訪每個陣列元素恰好一次。對於給定的陣列內容與起始方向,請輸出走訪順序之內容。
提示:本題有多種處理方式,其中之一是觀察每次轉向與走的步數。例如起始方向是向左時,前幾步的走法是:左 1、上 1、右 2、下 2、左 3、上 3、…… 一直到出界為止。
解題思路:
這題的提示真的太明顯,實在有點讓人來不及思考就把答案講出來了,正式考試應該沒有提示吧🤔
總之就是按照提示說的,每經過兩次不同方向移動就會多走一步,這邊要注意一點,最後走的那一次不會多走一步(以 3*3 來說,走的步數會是 1、1、2、2、2,而不是 1、1、2、2、3),要記得注意這個狀況。
因為這個過程每個點都只會被拜訪一次,總共有 \(N^2\) 個點,所以時間複雜度就會是 \(O(N^2)\),而且 \(N<50\),所以絕對不可能超時的👍
🌟因為是每經過兩次不同方向移動,這邊有一個小技巧,一開始把要走的步數設定成 10,每次 + 5,要用的時候再除以 10,寫起來會比較方便(或者是你可以用 double 一次增加 0.5,使用時再轉換成 int,但我比較不建議,雖然這題不會怎樣,但 double 能少用還是不要用,要不然如果太習慣,數字大了之後出現精度問題還要想辦法修正),另一點在移動的部分,可以開兩個陣列代表 x 移動方向跟 y 移動方向,然後依據目前方向代碼在陣列中索引移動方向(也可以開一個陣列同時兼顧 x 跟 y,雖然很酷但其實省這一點點空間根本沒差,所以還是推薦開兩個陣列會比較方便),當然如果你要開四個 if 跟迴圈也是可以的。
小插曲:我意外發現這題最後不換行也可以過
1 |
|
![AC的Submission~](https://i.imgur.com/1LqU1gf.png)