切換
舊版
前往
大廳
主題

ZeroJudge - d537: 4. 染色遊戲 解題心得

Not In My Back Yard | 2020-10-06 00:07:06 | 巴幣 2 | 人氣 412

題目連結:


題目大意:
輸入第一列給定一正整數 N (N ≦ 100),代表一個 N × N 格的白色畫布。

接著三列,每列給定一字元(只會是紅色「R」、黃色「Y」、藍色「B」、橘色「O」、紫色「P」、綠色「G」、黑色「D」這七種),以及兩整數,代表該顏色被滴在畫布上的位置。

假設這三種顏色同時滴到畫布上,且擴散速率一致、擴散的形式是以正方形從中心往外擴散。當畫布上有一格有多個顏色混雜在一起,則根據下圖判斷去決定顏色:

以下是每單位時間過後的擴散情況之範例:

最後一列給定一字元 X (可能字元同上),代表目標顏色。

試問顏色 X 曾經在畫布上佔有的最大單位面積為多少?



範例輸入:
輸入範例一:
5
Y 1 1
B 3 3
R 4 0
Y

輸入範例二:
5
Y 1 1
B 3 3
R 4 0
G


範例輸出:
輸出範例一:
8

輸出範例二:
9


解題思維:
可以將題目的七種顏色編碼為一個 3 位元長的二進位數字,例如最高位代表有無紅色、中間代表有無藍色、最低位為黃色等等。

因此上述方式之中
001 為黃色。
010 為藍色。
011 為綠色。
100 為紅色。
101 為橘色。
110 為紫色。
111 為黑色。

而顏色的混色,只需要將兩個顏色各自的編碼作或(OR) 運算即可。

對於每個時刻,掃過畫布每一格。用一個二維陣列 buffer 紀錄下一刻畫布的樣子,然後將每一格會擴散到的 buffer 對應位置(周圍八格)都與該格的顏色編碼作 OR 運算。

每格都掃完之後才將 buffer 的內容複製回原本的存畫布資訊的陣列裡。而且對於每一刻(包含初始的畫布之樣子)計算一下目標顏色 X 的數量。

X 的數量應該會先持續維持非嚴格遞增之狀態,接著會切換到非嚴格遞減。因此,當 X 的數量開始比上一刻時少,則上一刻 X 的數量即是所求。




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

創作回應

蔡蔡
版主您好,這個解法好像有點怪怪的,因為expand並不會每次都複製原本board上的情況,他只會複製change為true的情況而已,接下來你又把board上的情況全部改成跟expand一樣,這樣會讓原本有顏色的地方變成零,雖然會ac,但好像沒有很正確,不知道我這樣講有沒有誤會你的意思
2021-07-15 17:03:34
Not In My Back Yard
感謝指正,程式碼已更新。



同時也修正了當目標顏色根本不會出現在版面上時會陷入無限迴圈的情況XD

因為一個顏色最遠可以從左上角走到右下角,所以版面最多只會變動 2N - 1 次。

所以當迭代數到 2N 時就該停了。
2021-07-15 18:55:09
Not In My Back Yard
喔抱歉,他是正方形擴散。所以迭代次數最多只需要 N - 1 次。
2021-07-15 18:59:56
蔡蔡
喔,所以你這次是讓expand 先全部or = board 再去判斷change嗎?
2021-07-15 20:39:48
Not In My Back Yard
這樣應該就有解決假解的問題了,我猜
如果還有錯的話就再請指教了XD
2021-07-15 20:50:37
蔡蔡
謝謝,沒想到能幫到zerojudge解1000多題的大神xd
2021-07-15 21:05:48

相關創作

更多創作