主題

[leetcode]1931. Painting a Grid With Three Different Colors

???＼~O_O~／??? | 2021-08-18 12:00:23 | 巴幣 2 | 人氣 249

題目: 1931. Painting a Grid With Three Different Colors
難度: Hard
目前下列解法的時間複雜度: O( max(m,n)*(1<<(min(m,n))*? + pow(1<<(min(m,n),2) )

題目說明

給定一 m*n 的長方形，短邊不會超過 5 ，並且對齊邊緣切成 m*n 個 1x1 的正方形。
問使用3個顏色對正方形著色，相鄰(上下左右)正方形的顏色須不同，共幾種可能。

解法: dp

0. dp[排數][顏色組合] -> 填至該排數時，最後一排是該顏色組合的可能數 = sum( dp[排數-1][顏色組合_prev] if is_相鄰顏色皆不同(顏色組合_prev,顏色組合) )
1. 如果不好想的話，先想想這題 N*3 方格的題目
2. 如果還是很難想的話，想想看1*M 的情況 = 3*pow(2,M-1) 。
3. 每次增加新的一排時，對於該排某一種相鄰不同色顏色組合，從之前 1*M 的所有可能中，加總"上一排與此排符合相鄰不同顏色的可能數"。
4. 把表填完。
5. 把最後一排的答案加起來。

source code

然而

6. 每次只看前一排和這一排，不如把走過用不到的表切了吧。於是排數變成只有2。透過交換指標或類似的方式達成O(1)更新。

7. dp表其實不需要到 pow(3,短邊) 那麼寬，只要 3*pow(2,短邊) 就好了。
可以先定義顏色順序(0,1,2)，接著將顏色的編號視作在 mod 3 內的計算。
第1個顏色不改變(是0,1,2就是0,1,2) ；接下來的顏色，可以定義：
a. 0: 順序+1
b. 1: 順序-1
而超出邊界的自然就 mod 3 繞圈。
而且只用了0,1兩種東西，可以塞進1bit裡。
於是每次抓顏色只要 for(int x=0;x<(3<<(短邊-1));++x) 就好了。

8. 考慮短邊=5，每種顏色都要試，則：
首先你會花 3*3*3*3*3 在窮舉第一種顏色上，透過上面的剪枝剩下3*2*2*2*2。
接著再窮舉第二種顏色，透過剪枝剩下3*2*2*2*2。
兩邊乘起來 9*pow(2,8) ，再加上確認每一格顏色*5，再乘以排數1000，恭喜你！TLE，或是再多剪枝一下就過了。

9. 每一新排都做一樣的事，不如記下來，直接拿上次的結果，別再窮舉了一堆用不到的顏色組合了。這就是 source code 裡 mapping 的用途。

10. 然後一樣行為模式(指抓前一排答案的行為)的好像可以壓，但我不會。~~我只是看N*3那邊跑得很快的到底是怎麼寫的~~

~~11. 好像可以考慮矩陣快速冪耶~~矩陣 3*pow(2,短邊) by 3*pow(2,短邊) 好像不會比較好。