a055. Candy Crushhhhhhh

題目描述

伊藤蒼太打開了新遊戲「Candy Crushhhhhhh」！螢幕上擺著五種顏色的糖果；至少三顆同色糖果排成一列，就會「啪」地消失。上方的糖果往下掉，又可能碰巧排出下一列。他想知道，這個盤面會連鎖到第幾輪？

遊戲盤面有 R 個橫列、C 個直行，從上到下、從左到右排列。每個格子用一個數字表示：0 是空格，1 到 5 分別是五種顏色的糖果。數字相同的糖果顏色相同。

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

每一輪，遊戲會依序做以下事情：

1. 看目前的盤面，找出所有橫向、直向連線上的糖果。如果某顆糖果同時在兩條連線上，消除數量只算它一次。若一顆都找不到，遊戲結束，這次檢查不算一輪。
2. 所有找到的糖果同時消失，原本的位置變成 0。不可先消一條連線、讓糖果掉落，再找另一條連線。
3. 剩下的糖果沿著各自的直行往下掉，直到碰到盤面底部或其他糖果。同一直行內，原本在上面的糖果掉落後仍在原本下方糖果的上面；糖果不會左右移動。掉落後的空格集中在該直行的最上方。

掉落後若形成新連線，就進行下一輪，重新檢查整個盤面；直到找不到任何連線為止。本題的糖果已經擺好，不需要交換糖果，也不會從上方補進新糖果。

請幫伊藤蒼太算出一共消除了幾輪、多少顆糖果，以及最後盤面的樣子。

輸入格式

第一行有兩個正整數 R、C，分別代表盤面的橫列數與直行數。

接下來 R 行，從上到下給出每個橫列；每行有 C 個以一個空白隔開的整數，從左到右表示該列的格子。每個整數介於 0 到 5。

保證初始盤面沒有懸空的糖果：若某格是空格，它正上方的格子（若存在）也一定是空格。也就是說，每一直行的糖果都堆在最底下。

限制與子題

• 1 ≤ R, C ≤ 50
• 子題一（40 分）：C = 1。
• 子題二（60 分）：無額外限制。

輸出格式

第一行輸出兩個整數 K、S，以一個空白間隔。K 是實際發生消除的輪數，S 是所有輪次消除的糖果總數。同一顆糖果只計算一次；若一開始就沒有連線，則 K = 0、S = 0。

接下來輸出遊戲結束後的盤面，共 R 行，從上到下排列；每行 C 個整數，以一個空白間隔。空格仍以 0 表示。

範例一

範例輸入：

4 4
1 2 3 3
2 2 2 3
4 2 1 3
4 1 1 2

範例輸出：

1 8
0 0 0 0
1 0 3 0
4 0 1 0
4 1 1 2

第二橫列的三顆 2 和第二直行的三顆 2 形成十字形，中央那顆只算一次，所以一共會消掉 5 顆 2；第四直行上方的三顆 3 也會消失。第一輪同時消除 5 + 3 = 8 顆，糖果掉落後沒有新連線，遊戲結束。

範例二

範例輸入：

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

範例輸出：

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

初始盤面的第二直行有三顆連續的 1，第一輪消除這 3 顆。上方的 2 掉到第四橫列，和左右兩顆 2 排成一條新連線。第一輪掉落後的盤面是：

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

第二輪消除第四橫列的三顆 2，之後再也沒有連線。總共消除了 3 + 3 = 6 顆糖果，進行了 2 輪。