CCF 201604-2 俄罗斯方块

  • 作者:Moilk
  • 最后编辑:2016年09月09日
  • 标签: CCF 算法

问题描述
  俄罗斯方块是俄罗斯人阿列克谢·帕基特诺夫发明的一款休闲游戏。
  游戏在一个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

解题说明
  只要确定置入4x4方块时, 方块第一行在15x10游戏面板中的行数x就行。假设方块第i列从下往上扫描遇到的第一个1的行数为Bi, 显然Bi可以取0到4, 0表示这一列没有1; 再假设面板第j列从上往下扫描遇到的第一个1的行数为Tj,Tj可以取5到16, 16表示这一列没有1。这样, 如果将方块的第i列放入面板的第j列, 方块第1列在面板中的行数为Xi=(Bi?Tj-Bi:15)。最终, x=min(Xi)。

#include <iostream>

using namespace std;

bool board[16][15];
bool block[5][5];
int top[]={16,16,16,16,16};
int bottom[]={0,0,0,0,0};

int main(void){
	int pos;
	for(int i=1;i<=15;i++){
		for(int j=1;j<=10;j++){
			cin>>board[i][j];
		}
	}
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			cin>>block[i][j];
		}
	}
	cin>>pos;
	for(int j=1;j<=4;j++){
		for(int i=1;i<=15;i++){
			if(board[i][j+pos-1]){
				top[j]=i;
				break;
			}
		}
	}
	for(int j=1;j<=4;j++){
		for(int i=4;i>=1;i--){
			if(block[i][j]){
				bottom[j]=i;
				break;
			}
		}
	}
	
	int min=99;
	for(int i=1;i<=4;i++){
		int tmp=15;
		if(bottom[i]){
			tmp=top[i]-bottom[i];
		}
		if(tmp<min){
			min=tmp;
		}
	}
	
	for(int i=min;i<=15;i++){
		for(int j=pos;j<=pos+3;j++){
			if(block[i-min+1][j-pos+1]){
				board[i][j]=1;
			}
		}
	}
		
	for(int i=1;i<=15;i++){
		for(int j=1;j<=10;j++){
			cout<<board[i][j]<<' ';
		}
		cout<<endl;
	}
	
	return 0;
}