題目如下： 網上一般是模擬方塊下落的過程，這種方法簡潔，易於理解，代碼如下： 我剛開始的想法是，為什麼不從最後一行開始，那樣不是更快嗎？後來我發現這個想法不對，從下往上找，要一直遍歷到第0行，這樣的計算量特別大。 下麵，我說說自己的想法：先通過遍歷找到對應方塊在大矩陣中的最下麵一行，然後以這個行數為 ...
題目如下：
問題描述 俄羅斯方塊是俄羅斯人阿列克謝·帕基特諾夫發明的一款休閑游戲。 游戲在一個15行10列的方格圖上進行，方格圖上的每一個格子可能已經放置了方塊，或者沒有放置方塊。每一輪，都會有一個新的由4個小方塊組成的板塊從方格圖的上方落下，玩家可以操作板塊左右移動放到合適的位置，當板塊中某一個方塊的下邊緣與方格圖上的方塊上邊緣重合或者達到下邊界時，板塊不再移動，如果此時方格圖的某一行全放滿了方塊，則該行被消除並得分。 在這個問題中，你需要寫一個程式來模擬板塊下落，你不需要處理玩家的操作，也不需要處理消行和得分。 具體的，給定一個初始的方格圖，以及一個板塊的形狀和它下落的初始位置，你要給出最終的方格圖。 輸入格式 輸入的前15行包含初始的方格圖，每行包含10個數字，相鄰的數字用空格分隔。如果一個數字是0，表示對應的方格中沒有方塊，如果數字是1，則表示初始的時候有方塊。輸入保證前4行中的數字都是0。 輸入的第16至第19行包含新加入的板塊的形狀，每行包含4個數字，組成了板塊圖案，同樣0表示沒方塊，1表示有方塊。輸入保證板塊的圖案中正好包含4個方塊，且4個方塊是連在一起的（準確的說，4個方塊是四連通的，即給定的板塊是俄羅斯方塊的標準板塊）。 第20行包含一個1到7之間的整數，表示板塊圖案最左邊開始的時候是在方格圖的哪一列中。註意，這裡的板塊圖案指的是16至19行所輸入的板塊圖案，如果板塊圖案的最左邊一列全是0，則它的左邊和實際所表示的板塊的左邊是不一致的（見樣例） 輸出格式 輸出15行，每行10個數字，相鄰的數字之間用一個空格分隔，表示板塊下落後的方格圖。註意，你不需要處理最終的消行。 樣例輸入 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 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 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 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 3 樣例輸出 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 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 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 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0
網上一般是模擬方塊下落的過程，這種方法簡潔，易於理解，代碼如下：
#include<stdio.h> #include<stdlib.h> #include<iostream> using namespace std; struct Node{ int x; int y; }; int main() { int s[15][10]; Node t[4]; for(int i=0;i<15;i++) { for(int j=0;j<10;j++) { cin>>s[i][j]; } } int count=0; for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { int temp; cin>>temp; if(temp==1) { t[count].x=i; t[count].y=j; count++; } } } int col; cin>>col; if(col+4>=15) { return 0; }else{ for(int i=0;i<4;i++) { t[i].y+=col-1; } } int flag=0; while(1) { for(int i=0;i<4;i++) { if(s[t[i].x][t[i].y]) { flag=1; break; } } if(flag) { break; }else{ for(int i=0;i<4;i++) { t[i].x++; } } } if(flag==1) { for(int i=0;i<4;i++) { s[t[i].x-1][t[i].y]=1; } } for(int i=0;i<15;i++) { for(int j=0;j<10;j++) { cout<<s[i][j]<<" "; } cout<<endl; } return 0; }
我剛開始的想法是，為什麼不從最後一行開始，那樣不是更快嗎？後來我發現這個想法不對，從下往上找，要一直遍歷到第0行，這樣的計算量特別大。
下麵，我說說自己的想法：先通過遍歷找到對應方塊在大矩陣中的最下麵一行，然後以這個行數為標準來將圖形填充到大的矩陣中。詳細說明，在代碼中。
#include<stdio.h> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; struct Node{ int x; int y; int row; }; int cmp(Node x,Node y) { return x.x>y.x; } int main() { int s[15][10]; Node t[4]; Node temp[4];//在這裡t用作遍歷時的數組，temp主要是方便賦值 for(int i=0;i<15;i++) { for(int j=0;j<10;j++) { cin>>s[i][j]; } } int count=0; for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { int tem; cin>>tem; if(tem==1) { t[count].x=i; t[count].y=j; t[count].row=0; temp[count].x=i; temp[count].y=j; temp[count].row=0; count++; } } } int col; cin>>col; if(col+4>=15) { return 0; }else{ for(int i=0;i<4;i++) { t[i].y+=col-1; temp[i].y+=col-1; } } sort(t,t+4,cmp); sort(temp,temp+4,cmp); //-----------------找出最下麵的一行------------------------- int row,real_row; for(real_row=14;real_row>=0;real_row--){//一行一行的遍歷，從最底層開始。 row=real_row; int flag; for(;row>=0;row--)//將從最低行一直遍歷到第0行 { int temp_row=row; flag=0; for(int j=0;j<4;j++) { if(j==0){ if(temp_row<0){ break; } if(s[temp_row][t[j].y]==1){ flag=1;//標記失敗 break; }else{ temp_row=temp_row-t[j].x+t[j+1].x; } }else{ if(temp_row<0){ break; } if(s[temp_row][t[j].y]==1){ flag=1;//標記失敗 break; }else{ if(j<=2){ temp_row=temp_row-t[j].x+t[j+1].x; } } } } if(flag==1){//出現失敗後沒有必要在遍歷了，跳出迴圈，對下一個real_row進行從real_row到0的遍歷 break; } } if(flag==0){//說明出現了滿足情況的行數，停止執行。 break; } } //--------------重新賦值-------------------- // cout<<"最終行數為："<<real_row<<endl; for(int i=0;i<4;i++) { if(i==0){ temp[i].x=real_row; real_row=real_row-t[0].x+t[1].x; }else{ temp[i].x=real_row; if(i<=2){ real_row=real_row-t[i].x+t[i+1].x;//利用小矩陣中函數差，來確定對應的大矩陣中的行數，例如，t[0]在小矩陣中是第二行，t[1]在小矩陣中是第一行，t[0]在大矩陣中是第13行，那麼t[1]應該是13-2+1=12行 } } s[temp[i].x][temp[i].y]=1; } //--------------輸出結果-------------------- for(int i=0;i<15;i++) { for(int j=0;j<10;j++) { cout<<s[i][j]<<" "; } cout<<endl; } return 0; }
