CCF 201604-2 Tetris

subject

Problem description

　　 Tetris is Russian Alexei · Pajitnov invented a casual game .
　　 The game is in a 15 That's ok 10 On the grid of columns , Each grid on the grid may have placed squares , Or no square . Every round , There will be a new one 4 A plate composed of small squares falls from the top of the grid , Players can operate the plate to move left and right and put it in the right position , When the lower edge of a block in the plate coincides with the upper edge of the block on the grid or reaches the lower boundary , The plate no longer moves , If a row of the grid is full of squares , Then the line is eliminated and scored .
　　 In this case , You need to write a program to simulate the falling of plates , You don't have to deal with player operations , There is no need to deal with cancellation and scoring .
　　 Concrete , Given an initial grid , And the shape of a plate and the initial position where it falls , You have to give the final grid .

Input format

　　 Before entering 15 The row contains the initial grid , Each row contains 10 A digital , Adjacent numbers are separated by spaces . If a number is 0, Indicates that there are no squares in the corresponding square , If the number is 1, It means there are squares at the beginning . Before entering guarantee 4 The numbers in the line are 0.
　　 Input the 16 To 19 The row contains the shape of the newly added plate , Each row contains 4 A digital , Formed a plate pattern , Again 0 It means there is no square ,1 Indicates that there are squares . Input to ensure that the pattern of the plate just contains 4 Square block , And 4 The two squares are connected （ Accurately speaking ,4 The squares are four connected , That is, the given plate is the standard plate of Tetris ）.
　　 The first 20 The line contains a 1 To 7 Integer between , It indicates which column of the grid the leftmost part of the plate pattern starts from . Be careful , The plate pattern here refers to 16 to 19 The plate pattern entered in the row , If the leftmost column of the plate pattern is full of 0, Then its left side is inconsistent with the left side of the plate actually represented （ See Example ）

Output format

　　 Output 15 That's ok , Each row 10 A digital , Adjacent numbers are separated by a space , A square diagram showing the fall of a plate . Be careful , You don't have to deal with the final elimination .

The sample input

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

Sample output

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

---

Problem analysis

CCF It's terrible to start simulating the second problem , It's almost the first time I've done it before 2 The one that takes the longest time , I feel this kind of problem is very troublesome for me ~.

Say the main idea , It's like playing Tetris , The necessary and sufficient condition for the falling plate to stop is ： plate （ The plates here do not include all 0 The column of ） A column The bottom square Of The first position below The value of is 1. ok , Drawing is more intuitive ：

The frame in the figure with solid lines is the plate , The dotted line is the background . The blue part is the bottom square of each column of the plate , The orange one is the first square below the bottom square in each column . so , The sufficient and necessary condition for the plate to stop is that there is at least 1 Orange positions , Its value is 1, That is, the orange position has a square placed .

So the key to stopping is to find an orange position whose value is 1, Obviously, knowing the blue position can determine the orange position , And the blue position is part of the plate we input , So we just need Record the next position next to each blue position when inputting the plate . The method is ： Whenever we are in double for Loop in a 1 when （ There are squares here ）, Stool record low[j] = i+1, It means the first one j The orange position of the column is at i+1 That's ok , Because the order of our input is top-down , So the last low[] All the orange positions are recorded .

After finding the orange position , We judge whether there is an orange position with a value of 1, If you have any , Then stop . otherwise , For all columns j：low[j]++, It means that the whole plate moves down one line （ Of course, all orange positions move down one line at the same time ）, Then continue to repeatedly judge whether there is an orange position 1, Until it stops . In order to ensure that the plate reaches the bottom, it will stop , We can set a virtual line （ The first 16 That's ok ） And make the values of all columns be 1, This ensures the bottom （ The first 15 That's ok ） It will stop .

After the stop ,low[] The orange position is given , and low[] - 1 Is the blue position of the plate （ The bottom square of each column of plates ） Finally, it should be in the position in the figure . So we just need to know There are several squares in each column of the plate （ How many entries have been made in each column 1） The final position can be drawn , and When inputting blocks, count how many blocks there are in each column （ How many entries have been made in each column 1） It's very easy .

The last thing I want to roast out is Offset value shift Additional instructions for , It's really better not to say , It's easy to bring people into the ditch , Let's look at the examples .

Here's the code , The code idea is relatively clear ~

Code

#include<cstdio>
using namespace std;

int main(){
	int G[17][11];
	int low[5] = {0};// Record each column of the plate 1 Below 1 A place  
	int cnt[5] = {0};// Record each column in the block 1 Number of  
	int t,shift,i,j;
	
	for(i=1;i<=15;i++)
		for(j=1;j<=10;j++)
			scanf("%d",&G[i][j]);
	for(i=1;i<=10;i++)// sentry  
		G[16][i] = 1;
	
	for(i=1;i<=4;i++){
		for(j=1;j<=4;j++){
			scanf("%d",&t);
			if(t==1){
				low[j] = i + 1;
				cnt[j]++;
			}
		}
	}
	scanf("%d",&shift);
	
	bool stop = false;
	while(!stop){
		j = 0;
		for(i=1;i<=4;i++){
			if(cnt[i]==0)// Ignore columns that do not have squares  
				continue;
			if(G[low[i]][shift+i-1]==1){
				stop = true;
				break;
			}
		}
		if(!stop){// You can also move down one line  
			for(i=1;i<=4;i++)
				low[i]++;
		}
	}
	// here low[x]-1 It is the... In the plate x The bottom of the list 1 Line number of the placement position of  
	for(i=1;i<=4;i++){
		j = 0;
		while(cnt[i]--){
			G[low[i]-1-j][shift+i-1] = 1;
			j++;
		}
	}
	
	for(i=1;i<=15;i++){
		for(j=1;j<10;j++){
			printf("%d ",G[i][j]);
		}
		printf("%d\n",G[i][j]);
	} 
	
	return 0;
}