a056. Candy Crush 進階版

題目描述

伊藤蒼太這次要繼續來玩三消遊戲了！他可以交換相鄰的糖果，湊出三顆以上同色糖果，讓它們消失。空下來的位置會有糖果掉落、從上方補進新糖果；如果又排成一線，就繼續消除，直到整個盤面安靜下來，才輪到下一次交換。

盤面有 R 個橫列、C 個直行。最上面是第 1 橫列，最左邊是第 1 直行。每格的數字 1 到 5 表示五種不同顏色的糖果，0 表示空格。初始盤面每格都有糖果，而且沒有任何現成連線。

同一橫列中連續至少 3 顆左右相鄰的同色糖果，或同一直行中連續至少 3 顆上下相鄰的同色糖果，稱為一條連線。4 顆、5 顆或更多也算，整段都會消失；0 不能形成連線。

伊藤蒼太會依序嘗試 Q 次交換。每次指定兩個上下或左右相鄰的格子，依照下列規則處理：

1. 若任一格是空格，這次交換無效，盤面不變。否則先交換兩格的糖果。若交換後盤面上沒有任何連線，這次交換也無效，兩顆糖果立刻換回去。無效交換不消耗補充糖果，也不計分。
2. 如果交換後有連線，這次交換有效。以目前盤面為起點，進行連鎖消除：
   • 同時找出橫向與直向的所有連線。同一顆糖果即使在兩條連線的交叉處，也只算一次；將找到的糖果全部同時消除，變為 0。
   • 每個直行的剩餘糖果向下掉到底，同一直行糖果的上下順序不變，不會左右移動。
   • 接著從補糖序列取糖果，把各直行上方的空格補滿。依直行從左到右處理，同一直行的空格則由下到上填入；每補一格就使用序列中的下一顆糖果。例如一個直行上方有兩格空格，會先把下一顆放在較下面的空格，再把再下一顆放在最上面。
   • 若補完後又有連線，繼續下一輪「找連線、同時消除、掉落、補糖」。若補糖序列已用完，就讓無法補滿的格子保持 0。直到盤面上找不到連線，這次交換才算處理完畢，接著處理下一次交換。

計分方式：一次有效交換的第 1 輪消除，每消除一顆糖果得 1 分；第 2 輪每顆得 2 分；第 3 輪每顆得 3 分，依此類推。下一次有效交換的連鎖輪數重新從 1 開始。消除糖果的總數不乘上輪數。同一顆補充糖果只能使用一次；序列沒有用完的糖果也不計分。

請輸出有效交換的次數、消除的糖果總數、總得分，以及所有交換結束後的盤面。本題只模擬上述三消流程，沒有特殊糖果或其他道具。

輸入格式

第一行有四個整數 R C Q N：盤面的橫列數、直行數、交換次數、補糖序列的長度。

接下來 R 行，每行 C 個整數，表示由上到下、由左到右的初始盤面；每格介於 1 到 5。

若 N > 0，下一行有 N 個介於 1 到 5 的整數，依序是準備補進盤面的糖果。若 N = 0，沒有這一行。

最後 Q 行，每行四個整數 r_1 c_1 r_2 c_2，代表一次要交換的兩個格子，座標均從 1 開始。保證兩格在盤面內且上下或左右相鄰，但不保證該格目前有糖果。

限制與子題

• 1 ≤ R, C ≤ 20，且 R × C ≥ 2
• 1 ≤ Q ≤ 50
• 0 ≤ N ≤ 3000
• 保證初始盤面沒有任何連線。
• 子題一（40 分）：Q = 1 且 N = 0。
• 子題二（60 分）：無額外限制。

輸出格式

第一行輸出三個整數 V S P，依序代表有效交換次數、消除糖果總數與總得分。

接下來輸出最後的盤面，共 R 行，每行 C 個整數，以一個空白間隔；沒有糖果的格子輸出 0。

範例一

範例輸入：

3 3 1 0
1 2 1
2 1 2
3 2 3
1 2 2 2

範例輸出：

1 6 6
0 0 0
0 0 0
3 2 3

交換第一、二橫列中間的糖果後，上面兩橫列分別變成 1 1 1 與 2 2 2。兩條連線同時消除，總共 6 顆；沒有補充糖果，所以盤面上方留下空格。本次交換只有一輪消除，得 6 分。

範例二

範例輸入：

4 3 2 6
1 2 1
2 1 2
3 2 3
4 4 5
3 1 3 2 3 1
1 2 2 2
3 1 3 2

範例輸出：

1 9 12
0 0 0
1 2 1
3 2 3
4 4 5

第一次交換先同時消除 6 顆。掉落後，每一直行有兩個空格；補糖時，第一直行由下到上放入 3、1，第二直行放入 3、2，第三直行放入 3、1。此時第二橫列的 3 3 3 形成新連線，第二輪再消除 3 顆。總分是 6 × 1 + 3 × 2 = 12。

第二次想交換第三橫列的前兩格，但交換後沒有連線，因此會換回去。只有第一次交換有效，最後一共消除 9 顆。