摘要：之前介紹，機試題主要考察分析和邏輯能力，不會用到復雜的算法，而且現場也不能使用除了輸入輸出流之外的其他的庫或包。判斷條件為，實際調試時出錯，這塊分析不嚴謹。

3月1日，三星電子研究所公司機試。
之前HR介紹，機試題主要考察分析和邏輯能力，不會用到復雜的算法，而且現場也不能使用除了輸入輸出流之外的其他的庫或包。

在公司的一間機試屋子考試，有VisualStudio和Eclipse兩種編譯器可選。機試有專門的系統，可以查看題目，并且在下方編程（沒有提示，得全程手打，而且不提醒語法錯誤，建議用編譯器），該頁面同時可以進行測試案例調試，運行后可得編譯結果（會提示語法錯誤和異常）提供參考。調試次數不限，提交（submit）次數為三次，提交后，屏幕會彈出本地10個case的通過情況，通過為pass，后臺還有其他case，所以最終結果還得等總部過幾天的反饋。機試總共3小時，系統界面和題目都是英語，手機得飛行模式，現場提供紙筆。

原題記不太清了，大致意思如下：
給一個10×10的表格（grid），其中放置有2×1的方塊（blocks），方塊和橫豎放置。讓表格中的方塊自由下落（類似俄羅斯方塊），堆積在底部。表格中有方塊占有的格子用1表示，沒有的用0表示。用數字0-10表示下落后，每列的方塊高度。

圖1：方塊降落前

圖2：方塊降落后

注：題目要求方塊不能全部靠在左側、右側、上側或下側，而且下邊這種連續放置方塊的情況也不允許（題目中英文沒全看懂，個人理解）。這個條件尤其要注意，中途寫完程序，就是忽略了這個約束，結果老是不對。

1、Input

0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0
0  0  0  1  0  0  0  1  1  0   
0  0  0  1  0  0  0  0  0  0  
1  1  0  0  0  0  0  0  0  0  
0  0  0  0  1  1  0  0  0  0  
0  1  1  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  1  0  0  
0  0  0  0  0  0  0  1  0  0  
0  0  0  0  0  0  0  0  0  0
…… 
共10個case

2、Output

*1 2212110330 
…… 
10個case，每個case的結果都按行輸出(*1表示case1）

首先，本題是計算落下方塊的高度。從下往上，方塊是堆疊起來的，也就是說，上層的方塊降落點取決于下層的方塊位置。因此，思路是從下向上，按行迭代分析。再將問題拆解，每行迭代的時候，可以從左向右分析。

設輸入表格元素數組為A11，輸出的高度數組為height[11]，兩者都從1迭代（輸入從索引1開始賦值）。

比如：圖1第一行，從A10到A10，遍歷后，數值都為0，則當前的每列高度都為0，height[k]=0;從第二行開始，A9的元素就變為1，height[8]=1,實際的輸入case情況復雜，因此需要定義遍歷計算的規則。

按照上訴思路，構建兩層for循環，外層i：10~1，內層j：1-10。對于2×1的方塊，有兩種下落姿態，水平和豎直放置下落。對于豎直下落而言，無論下方多么復雜，該方塊永遠都是直接落在過程中第一個看到的方塊。在迭代時，對于豎直下落方塊，每行直接對height加1即可。

對于水平放置方塊，情況比較復雜。首先方塊橫向是一個整體，下落位置受兩個子塊下方堆疊情況影響。作圖分析：

當前迭代列為j，首先考慮當前為1的方格（黑色），其構成的方塊的另一半，在其左側還是右側。如果在右側，右側的方塊子塊降落會由當前子塊決定，不用分析。如果在左側，那么當前子塊的落點取決于左側兄弟子塊的下方和當前列下方情況。自然的，如果左高右低，那么橫塊將搭在左側，右側子塊落點同左側。判斷條件為：if(height[j-1]>height[j])，實際調試時出錯，這塊分析不嚴謹。
實際情況如下：

由于當前子塊與左側子塊相連，迭代到當前列i時，左側子塊對應的height[j]已進行自加，實際條件應為：height[j-1]-1 > height[j]。也就是說，左側height減1后，與右側height大小，若左側大，height[j]=height[j-1]。否則height[j]自加。

由于對第i列迭代時，直接操作左右兩側的Ai和height[j-1]，調試時發生數組索引越界異常。因此在循環內部，首先處理兩種特殊情形：

簡化案例輸入過程，直接在主函數定義一個case數組，方法也直接寫在主函數中。

public class ExamSamsun {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[][] A={{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0},
            {0,0,0,0,1,0,0,0,1,1,0},{0,0,0,0,1,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0,0},
            {0,0,0,0,0,1,1,0,0,0,0},{0,0,1,1,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,1,0,0},
            {0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,0,0,0,0}};
        
                
        int[] height=new int[11];  //測試例結果應為1 1 2 2 1 2 1 1 0 3 0 0 
        for(int i=10;i>=1;i--) {
            for(int j=1;j<=10;j++) {
                if(A[i][j]==1) {
                    //特殊情況
                    if(j==1&&A[i][j+1]==1) {
                        if(height[j+1]>height[j])
                            height[j]=height[j+1]+1;
                        else
                            height[j]++;
                        continue; //當前列已迭代完，執行下列
                    }                        
                    if(j==10&&A[i][j]==1) {
                        if(height[j-1]-1>height[j])
                            height[j]=height[j-1];
                        else
                            height[j]++;
                        continue;
                    }
                    //一般情形
                    if(j>=2&&j<=9) {
                        if(A[i][j-1]==1) {
                            if(height[j-1]-1>height[j])
                                height[j]=height[j-1];
                            else
                                height[j]++;
                            continue;
                        }
                        
                        if(A[i][j+1]==1) {
                            if(height[j+1]>height[j])
                                height[j]=height[j+1]+1;
                            else
                                height[j]++;
                            continue;
                        }
                        height[j]++;
                    }
                    
                }
                
            }//inner
        }//outer
            
        
        //output
        for(int i=1;i<=10;i++)
            System.out.print(height[i]+" ");
        }

}

寫完后，又想了一遍，覺得對當前Ai=1的格子向前判斷似乎重復了，后續有空再簡化下程序。