/*iAkiak热衷于网络俄罗斯方块对战游戏。为了能够赢得更多的比赛，他决定编写一个俄罗斯方块的外挂程序。他希望这个程序能够尽快的把游戏中所有的方块消除。
虽然俄罗斯方块游戏几乎耳熟能详、人尽皆知，但为了让大家明确，还是先介绍一下：
俄罗斯方块游戏内有19种不同的4*4的方块组合。每种组合都只有4个连续的有效方块（用*表示），其余部分是空白方块（用0表示）。有的方块仅仅是其他方块旋转得到的。下面列举出所有19种方块，为了便于讨论，给它们依次编号0..18：
**** *000
0000 *000
0000 *000
0000 *000
(0) (1)
0*00 0*00 ***0 *000
***0 **00 0*00 **00
0000 0*00 0000 *000
0000 0000 0000 0000
(2) (3) (4) (5)
0**0 *000 **00 0*00
**00 **00 0**0 **00
0000 0*00 0000 *000
0000 0000 0000 0000
(6) (7) (8) (9)
**00
**00
0000
0000
(10)
*000 00*0 **00 ***0
*000 ***0 0*00 *000
**00 0000 0*00 0000
0000 0000 0000 0000
(11) (12) (13) (14)
0*00 ***0 **00 *000
0*00 00*0 *000 ***0
**00 0000 *000 0000
0000 0000 0000 0000
(15) (16) (17) (18)
游戏区域是一个(9列*20行的矩阵，游戏开始时，游戏区域的下半部分（10行）随机的存在一些有效方块，上半部分则完全是空白方块。玩家一次移动一个系统给定的方块，初始位置为20行之上的任意一列。玩家可以旋转方块，当方块下落接触其他有效方块时该方块成为游戏区域内的方块。任意时候，游戏区域内的有效方块占满一行即可消去。
iAkiak发现，由于这个游戏本身的漏洞，玩家其实可以选择任意的19个方块组合之一作为下一个使用的方块组合。因此，可以简化外挂逻辑的设计：
这个外挂的逻辑程序可以选择任意19个方块组合之一，从任意列进入游戏区域，并一路下落直到接触其他有效方块(下落过程中，不做任何左右移动)。选一个方块放入游戏区域这个过程为一步操作。为了尽快结束战斗，iAkiak希望这个步骤数量尽量少。
现在需要你来为iAkiak编写这个逻辑程序。
int Calc(const char map[20][9], char outCmd[1000][2]);
函数Calc读取map初始信息，其中只包含'0'和'*'。
将结果写入数组outCmd，并返回总共的执行步数。
outCmd最多能存放1000组数据，每组包括2个元素
outCmd[i][0]表示第i步选择的方块代号（必须是[0..18]之一，否则当作该组测试数据不通过）
outCmd[i][1]表示第i步方块放的列位置（必须是[0..8]之一，并且根据选择的方块，保证不能有有效方块放到游戏区域之外，否则当作该组测试数据不通过）游戏过程中把有效方块堆到界外也算未通过测试。
列位置是选择的方块的最左侧有效方块放到游戏区域内所在的列。
如果1000步内未能消除所有方块，则返回-1，表示放弃该组测试数据。（注意：放弃的不算通过数据，但可以得1分）
如果越界访问outCmd则判为该组测试数据不通过。
如果2秒内该函数仍然不能正常返回，则作为未通过测试。
iAkiak看到这么多朋友都来帮助他写程序，觉得非常高兴。但他希望能够找到最好的程序，为此他设计了判断各个程序好坏的标准：
1. 所有参加的朋友只选用他提供的多个代码中最好的一个参与判断（如果你贴了多个代码，我将以为你最后贴的一个是你自己觉得最好的程序）
2. 每个程序都参与测试所有的数据（保证合法并且每个程序所得到的数据都一致）完全随机生成的20组。（如果某组数据没有人通过，则另外加一组替换，保证有效的测满20组）
3. 一个程序在一组数据上的得分的计算：
通过该组数据的所有程序都有一个返回值，表示它需要的最少步数（不通过的程序不得分，并且不参与计算平均分）
假设所有通过程序的步数的平均值为a,某个程序的步数为k，则该程序该组的得分是:(100 * (a - k)/a)^2
返回步数比平均步数多的得0分。得分精确到整数（截取，不要四舍五入）
4. 每个程序的各组数据的得分相加得到总分。（其中负分不记入总分）
5. 按照总分由高到低排列。
计算各程序得分的程序：
int CalcScore(const int result[], int n, int score[]);
CalcScore计算一组测试数据，n个程序的得分情况，结果存放在score内。
result[i]是第i个程序的返回步数
如果result[i]小于0，则该程序未通过测试。
返回值表示该组数据通过的人数。（注意，不是得分的人数）
第一题
实现CalcScore函数。result保证在[-1,1000]之内，n在[1,1000]内。
第二题
实现Calc函数。map内只包含字符'0'和'*'，并且只有map[0]到map[9]之间的10行内可能包含字符'*'。
*/
/*算法思路：
* 1。创建一个俄罗斯方块类，把把原地图拷贝到类的对象中。
* 2。检先检查游戏区域是否有空行，若有将其消去（空行上方的方块依次向下移动覆盖下面的方块）；
再检查是否有满行，若有，则将其变成空行。
* 3。读取各列的高度，即从最高行开始往下的连续空方块数。找到最大高度所在的列，返回起其列号。
* 4。根据返回的列极其周围列高度的分布情况，按照事先设定优先顺序选择添加对应的模块，
并将模块移动到相应的位置。将模块信息写入outCmd[1000][2]。
* 5。重复步骤2-4，直到所有的行都为空行，返回总共的执行步数，结束CalcScore()程序。
或者当模块数超过999时，则返回-1，表示放弃该组测试数据。
* 6。为了应付各种情况，我准备了4套方案。因为4套方案各有所长，故依次先后运行，取较好的数据。
选择最好的数据返回。
* 6。可以打印任意时刻的地图，以观察变化情况。
*/
#include <iostream>
using namespace std;
const int MaxRow = 20; //最大行数
const int MaxCol = 9; //最大列数
///////////////////////////////////////////////////////////////////////////////
class Diamond{ //俄罗斯方块类
char map[MaxRow][MaxCol]; //存储地图
public:
Diamond (const char map[][MaxCol]); //构造函数，把原地图拷贝到对象中
void PrintMap(); //输出地图
int Check(); //检查是否有满行，若有，则将其变成空行，并消去空行---上面的方块向下移动覆盖空行
bool IsFull(int row); //检查该行是否为满行（全部为'*'）
bool IsEmpty(int row); //将该行设置为空行
void MakeEmpty(int row); //检查该行是否为空行（全部为'0'）
void MoveWhole(int row); //移动整个地图（在出现空行时发生）
void MovePart(int row, int col, int height); //移动某一列的部分方块
int GetHeight(int row, int col); //读取该列的高度，即从row行开始往下的连续空方块数(不包括row）
int GetHighestCol(); //返回地图中的最大高度所在的列
int Choose1(int hCol);//按照设定的优先顺序选择对应的模块，返回模块的编号
int Choose2(int hCol);//按照设定的优先顺序选择对应的模块，返回模块的编号
int Choose3(int hCol);//按照设定的优先顺序选择对应的模块，返回模块的编号
int Choose4(int hCol);//按照设定的优先顺序选择对应的模块，返回模块的编号
void GetShape(int choice, int hCol);//根据模块的编号，将对应的模块加入到地图中
// 对应各种模块所采取的操作：添加模块，并移动到相应的位置
void Shape0(int hCol);
void Shape1(int hCol);
void Shape2(int hCol);
void Shape3(int hCol);
void Shape4(int hCol);
void Shape5(int hCol);
void Shape6(int hCol);
void Shape7(int hCol);
void Shape8(int hCol);
void Shape9(int hCol);
void Shape10(int hCol);
void Shape12(int hCol);
void Shape13(int hCol);
void Shape14(int hCol);
void Shape16(int hCol);
void Shape17(int hCol);
void Shape18(int hCol);
};
///////////////////////////////////////////////////////////////////////////////
Diamond::Diamond (const char map[][MaxCol])
{
for (int i=0; i<MaxRow; i++)
for (int j=0; j<MaxCol; j++)
Diamond::map[i][j] = map[i][j];
// PrintMap();
}
void Diamond::PrintMap()
{
cout << "\n";
for (int i=MaxRow-1; i>=0; i--)
{
for (int j=0; j<MaxCol; j++)
cout << map[i][j];
cout << "\n";
}
}
int Diamond::Check()
{
while (1)
{
for (int i=0; i<MaxRow; i++)
{
if (IsEmpty(i) && IsEmpty(i+1))//若i行上面没有非空行，表示已经出了游戏区域
return i;
else if (IsEmpty(i) && !IsEmpty(i+1)) //若i行上面还有非空行，方块下移覆盖i行
{
MoveWhole(i); // PrintMap();getchar();
break;
}
else if (IsFull(i)) //若i行为满行，将其设置为空行
{ // PrintMap();getchar();
MakeEmpty(i);
break;
}
}
}
}
bool Diamond::IsFull(int row)
{
for (int j=0; j<MaxCol; j++)
if (map[row][j] == '0')
return false;
return true;
}
bool Diamond::IsEmpty(int row)
{
for (int j=0; j<MaxCol; j++)
if (map[row][j] == '*')
return false;
return true;
}
void Diamond::MakeEmpty(int row)
{
for (int j=0; j<MaxCol; j++)
map[row][j] = '0';
}
int Diamond::GetHeight(int row, int col)
{
int height = 0;
for (int i=row-1; i>=0; i--) //累积从row-1行开始往下的连续空方块数，即该列的“高度”
{
if (map[i][col] == '0')
height++;
else
break;
}
return height;
}
int Diamond::GetHighestCol()//返回具有最大“高度”的列
{
int max = 0;
int hCol = 0;
for (int j=0; j<MaxCol; j++)
{
int height = GetHeight(MaxRow-1, j); //读取该列的高度
if (max < height)
{
max = height;
hCol = j;
}
}
return hCol;
}
void Diamond::MoveWhole(int row)//以i行为参照，移动整个地图row行为空行
{
for (int j=0; j<MaxCol; j++)
{
MovePart(row, j, 0);
}
}
void Diamond::MovePart(int row, int col, int Height)
{
for (int i=row; i+1<MaxRow; i++)//将row行上方的方块下移
{
map[i-Height][col] = map[i+1][col];
map[i+1][col] = '0'; //方块被移走后，该处变成空
}
}
int Diamond::Choose1(int hCol) //按照优先顺序选择对应的模块
{
int h = GetHeight(MaxRow-1, hCol); //读取hCol列的高度
int hleft1 = MaxRow; //位于hCol列左边第1列的高度
int hleft2 = MaxRow; //位于hCol列左边第2列的高度
int hright1 = MaxRow; //位于hCol列右边第1列的高度
int hright2 = MaxRow; //位于hCol列右边第2列的高度
int hright3 = MaxRow; //位于hCol列右边第3列的高度
if (hCol > 0) //读取hCol列左边第1列的高度
hleft1 = GetHeight(MaxRow-1, hCol-1);
if (hCol > 1) //读取hCol列左边第2列的高度
hleft2 = GetHeight(MaxRow-1, hCol-2);
if (hCol < 6) //读取hCol列右边第3列的高度
hright3 = GetHeight(MaxRow-1, hCol+3);
if (hCol < 7) //读取hCol列右边第2列的高度
hright2 = GetHeight(MaxRow-1, hCol+2);
if (hCol < 8) //读取hCol列右边第1列的高度
hright1 = GetHeight(MaxRow-1, hCol+1);
/////////////按照优先顺序选择对应的模块//////////////////////////////////
/*
A 若j的右边有连续3列与它高度相同，选择方块（0），从j降落。
B 若j==0，且其右边比他“低”3格；或j==8，且其左边比他“低”3格；（或更多）
或j在中间，且其左右两边都比他“低”3格。则选择方块（1），从j降落。
C 若j的右边有连续2列与它高度相同，
若j==0，选择方块（18），从j降落；
若j==6，选择方块（12），从j降落；
否则， 选择方块（2），从j降落。
D 若j的右边第1列与他高度相同，
若比左边的高2，比右边第2列高1，选择方块（6），从j降落；
若比左边的高1，比右边第2列高2，选择方块（8），从j降落；
否则，选择方块（10），从j降落。
E 若j>0，且其左边比他“低”2格，选择方块（13），从j降落。
F 若j<8，且其右边比他“低”2格，选择方块（17），从j降落。
G 若j的左边有连续2列都比它“低”1格，选择方块（16），从j降落；
H 若j的右边有连续2列都比它“低”1格，选择方块（14），从j降落；
I 若j的左右两边都比它“低”1格，选择方块（4），从j降落；
若j的右边比它“低”1格，选择方块（5），从j降落；
若j的左边比它“低”1格，选择方块（3），从j降落。
*/
if (hCol < 6 && h == hright1 && h == hright2 && h == hright3)
return 0;
else if ((hCol == 0 && h-hright1>=3)
|| (hCol == 8 && h-hleft1>=3)
|| (hCol > 0 && hCol < 8 && h-hright1>=3 && h-hleft1>=3))
return 1;
else if (hCol == 0 && h == hright1 && h == hright2)
return 18;
else if (hCol == 6 && h == hright1 && h == hright2)
return 12;
else if (hCol < 6 && h == hright1 && h == hright2)
return 2;
else if (h == hright1)
{
if ((h-hright2 ==1) && ((hCol < 7 && h-hleft1 >= 2) || hCol ==7))
return 6;
else if ((h-hleft1 == 1) && ((hCol > 1 && h-hright2 >= 2) || hCol ==1))
return 8;
else
return 10;
}
else if (hCol > 0 && h-hleft1==2)
return 13;
else if (hCol < 8 && h-hright1==2)
return 17;
else if (hCol > 1 && h-hleft1==1 && h-hleft2==1)
return 16;
else if (hCol < 7 && h-hright1==1 && h-hright2==1)
return 14;
else if (hCol > 0 && hCol < 8 && h-hright1==1 && h-hleft1==1)
return 4;
else if (hCol > 0 && h-hleft1==1)
return 3;
else if (hCol < 8 && h-hright1==1)
return 5;
}
int Diamond::Choose2(int hCol) //按照优先顺序选择对应的模块
{
int h = GetHeight(MaxRow-1, hCol); //读取hCol列的高度
int hleft1 = MaxRow; //位于hCol列左边第1列的高度
int hleft2 = MaxRow; //位于hCol列左边第2列的高度
int hright1 = MaxRow; //位于hCol列右边第1列的高度
int hright2 = MaxRow; //位于hCol列右边第2列的高度
int hright3 = MaxRow; //位于hCol列右边第3列的高度
if (hCol > 0) //读取hCol列左边第1列的高度
hleft1 = GetHeight(MaxRow-1, hCol-1);
if (hCol > 1) //读取hCol列左边第2列的高度
hleft2 = GetHeight(MaxRow-1, hCol-2);
if (hCol < 6) //读取hCol列右边第3列的高度
hright3 = GetHeight(MaxRow-1, hCol+3);
if (hCol < 7) //读取hCol列右边第2列的高度
hright2 = GetHeight(MaxRow-1, hCol+2);
if (hCol < 8) //读取hCol列右边第1列的高度
hright1 = GetHeight(MaxRow-1, hCol+1);
/////////////按照优先顺序选择对应的模块//////////////////////////////////
/*
A 若j的右边有连续3列与它高度相同，选择方块（0），从j降落。
B 若j==0，且其右边比他“低”3格；或j==8，且其左边比他“低”3格；（或更多）
或j在中间，且其左右两边都比他“低”3格。则选择方块（1），从j降落。
C 若j的右边有连续2列与它高度相同，
若j==0，选择方块（18），从j降落；
若j==6，选择方块（12），从j降落；
否则， 选择方块（2），从j降落。
D 若j的右边第1列与他高度相同，
若比左边的高2，比右边第2列高1，选择方块（6），从j降落；
若比左边的高1，比右边第2列高2，选择方块（8），从j降落；
否则，选择方块（10），从j降落。
E 若j的左边有连续2列都比它“低”1格，选择方块（16），从j降落；
F 若j的右边有连续2列都比它“低”1格，选择方块（14），从j降落；
G 若j>0，且其左边比他“低”2格，选择方块（13），从j降落。
H 若j<8，且其右边比他“低”2格，选择方块（17），从j降落。
I 若j的左右两边都比它“低”1格，选择方块（4），从j降落；
若j的右边比它“低”1格，选择方块（5），从j降落；
若j的左边比它“低”1格，选择方块（3），从j降落。
*/
if (hCol < 6 && h == hright1 && h == hright2 && h == hright3)
return 0;
else if ((hCol == 0 && h-hright1>=3)
|| (hCol == 8 && h-hleft1>=3)
|| (hCol > 0 && hCol < 8 && h-hright1>=3 && h-hleft1>=3))
return 1;
else if (hCol == 0 && h == hright1 && h == hright2)
return 18;
else if (hCol == 6 && h == hright1 && h == hright2)
return 12;
else if (hCol < 6 && h == hright1 && h == hright2)
return 2;
else if (h == hright1)
{
if ((h-hright2 ==1) && ((hCol < 7 && h-hleft1 >= 2) || hCol ==7))
return 6;
else if ((h-hleft1 == 1) && ((hCol > 1 && h-hright2 >= 2) || hCol ==1))
return 8;
else
return 10;
}
else if (hCol > 1 && h-hleft1==1 && h-hleft2==1)
return 16;
else if (hCol < 7 && h-hright1==1 && h-hright2==1)
return 14;
else if (hCol > 0 && h-hleft1==2)
return 13;
else if (hCol < 8 && h-hright1==2)
return 17;
else if (hCol > 0 && hCol < 8 && h-hright1==1 && h-hleft1==1)
return 4;
else if (hCol > 0 && h-hleft1==1)
return 3;
else if (hCol < 8 && h-hright1==1)
return 5;
}
int Diamond::Choose3(int hCol) //按照优先顺序选择对应的模块
{
int h = GetHeight(MaxRow-1, hCol); //读取hCol列的高度
int hleft1 = MaxRow; //位于hCol列左边第1列的高度
int hleft2 = MaxRow; //位于hCol列左边第2列的高度
int hright1 = MaxRow; //位于hCol列右边第1列的高度
int hright2 = MaxRow; //位于hCol列右边第2列的高度
int hright3 = MaxRow; //位于hCol列右边第3列的高度
if (hCol > 0) //读取hCol列左边第1列的高度
hleft1 = GetHeight(MaxRow-1, hCol-1);
if (hCol > 1) //读取hCol列左边第2列的高度
hleft2 = GetHeight(MaxRow-1, hCol-2);
if (hCol < 6) //读取hCol列右边第3列的高度
hright3 = GetHeight(MaxRow-1, hCol+3);
if (hCol < 7) //读取hCol列右边第2列的高度
hright2 = GetHeight(MaxRow-1, hCol+2);
if (hCol < 8) //读取hCol列右边第1列的高度
hright1 = GetHeight(MaxRow-1, hCol+1);
/////////////按照优先顺序选择对应的模块//////////////////////////////////
/*
A 若j的右边有连续3列与它高度相同，选择方块（0），从j降落。
B 若j==0，且其右边比他“低”3格；或j==8，且其左边比他“低”3格；（或更多）
或j在中间，且其左右两边都比他“低”3格。则选择方块（1），从j降落。
C 若j的右边有连续2列与它高度相同，
若j==0，选择方块（18），从j降落；
若j==6，选择方块（12），从j降落；
否则， 选择方块（2），从j降落。
D 若j的右边第1列与他高度相同，
若比左边的高2，比右边第2列高1，选择方块（6），从j降落；
若比左边的高1，比右边第2列高2，选择方块（8），从j降落；
否则，选择方块（10），从j降落。
E 若j==1，且其左边的列比它“低”1格，或者j>1，且其左边的第1列比它“低”1格，
左边的第2列比它“低”2格，选择方块（7），从j降落；
F 若j==7，且其右边的列比它“低”1格，或者j<7，且其右左边的第1列比它“低”1格，
右边的第2列比它“低”2格，选择方块（9），从j降落；
G 若j>0，且其左边比他“低”2格，选择方块（13），从j降落。
H 若j<8，且其右边比他“低”2格，选择方块（17），从j降落。
I 若j的左边有连续2列都比它“低”1格，选择方块（16），从j降落；
G 若j的右边有连续2列都比它“低”1格，选择方块（14），从j降落；
K 若j的左右两边都比它“低”1格，选择方块（4），从j降落；
若j的右边比它“低”1格，选择方块（5），从j降落；
若j的左边比它“低”1格，选择方块（3），从j降落。
*/
if (hCol < 6 && h == hright1 && h == hright2 && h == hright3)
return 0;
else if ((hCol == 0 && h-hright1>=3)
|| (hCol == 8 && h-hleft1>=3)
|| (hCol > 0 && hCol < 8 && h-hright1>=3 && h-hleft1>=3))
return 1;
else if (hCol == 0 && h == hright1 && h == hright2)
return 18;
else if (hCol == 6 && h == hright1 && h == hright2)
return 12;
else if (hCol < 6 && h == hright1 && h == hright2)
return 2;
else if (h == hright1)
{
if ((h-hright2 ==1) && ((hCol < 7 && h-hleft1 >= 2) || hCol ==7))
return 6;
else if ((h-hleft1 == 1) && ((hCol > 1 && h-hright2 >= 2) || hCol ==1))
return 8;
else
return 10;
}
else if ((hCol == 1 && h-hleft1==1)||(hCol > 1 && h-hleft1==1 && h-hleft2==2))
return 7;
else if ((hCol == 7 && h-hright1==1)||(hCol < 7 && h-hright1==1 && h-hright2==2))
return 9;
else if (hCol > 0 && h-hleft1==2)
return 13;
else if (hCol < 8 && h-hright1==2)
return 17;
else if (hCol > 1 && h-hleft1==1 && h-hleft2==1)
return 16;
else if (hCol < 7 && h-hright1==1 && h-hright2==1)
return 14;
else if (hCol > 0 && hCol < 8 && h-hright1==1 && h-hleft1==1)
return 4;
else if (hCol > 0 && h-hleft1==1)
return 3;
else if (hCol < 8 && h-hright1==1)
return 5;
}
int Diamond::Choose4(int hCol) //按照优先顺序选择对应的模块
{
int h = GetHeight(MaxRow-1, hCol); //读取hCol列的高度
int hleft1 = MaxRow; //位于hCol列左边第1列的高度
int hleft2 = MaxRow; //位于hCol列左边第2列的高度
int hright1 = MaxRow; //位于hCol列右边第1列的高度
int hright2 = MaxRow; //位于hCol列右边第2列的高度
int hright3 = MaxRow; //位于hCol列右边第3列的高度
if (hCol > 0) //读取hCol列左边第1列的高度
hleft1 = GetHeight(MaxRow-1, hCol-1);
if (hCol > 1) //读取hCol列左边第2列的高度
hleft2 = GetHeight(MaxRow-1, hCol-2);
if (hCol < 6) //读取hCol列右边第3列的高度
hright3 = GetHeight(MaxRow-1, hCol+3);
if (hCol < 7) //读取hCol列右边第2列的高度
hright2 = GetHeight(MaxRow-1, hCol+2);
if (hCol < 8) //读取hCol列右边第1列的高度
hright1 = GetHeight(MaxRow-1, hCol+1);
/////////////按照优先顺序选择对应的模块//////////////////////////////////
/*
A 若j的右边有连续3列与它高度相同，选择方块（0），从j降落。
B 若j==0，且其右边比他“低”3格；或j==8，且其左边比他“低”3格；（或更多）
或j在中间，且其左右两边都比他“低”3格。则选择方块（1），从j降落。
C 若j的右边有连续2列与它高度相同，
若j==0，选择方块（18），从j降落；
若j==6，选择方块（12），从j降落；
否则， 选择方块（2），从j降落。
D 若j的右边第1列与他高度相同，
若比左边的高2，比右边第2列高1，选择方块（6），从j降落；
若比左边的高1，比右边第2列高2，选择方块（8），从j降落；
否则，选择方块（10），从j降落。
E 若j==1，且其左边的列比它“低”1格，或者j>1，且其左边的第1列比它“低”1格，
左边的第2列比它“低”2格，选择方块（7），从j降落；
F 若j==7，且其右边的列比它“低”1格，或者j<7，且其右左边的第1列比它“低”1格，
右边的第2列比它“低”2格，选择方块（9），从j降落；
G 若j的左边有连续2列都比它“低”1格，选择方块（16），从j降落；
H 若j的右边有连续2列都比它“低”1格，选择方块（14），从j降落；
I 若j>0，且其左边比他“低”2格，选择方块（13），从j降落。
J 若j<8，且其右边比他“低”2格，选择方块（17），从j降落。
K 若j的左右两边都比它“低”1格，选择方块（4），从j降落；
若j的右边比它“低”1格，选择方块（5），从j降落；
若j的左边比它“低”1格，选择方块（3），从j降落。
*/
if (hCol < 6 && h == hright1 && h == hright2 && h == hright3)
return 0;
else if ((hCol == 0 && h-hright1>=3)
|| (hCol == 8 && h-hleft1>=3)
|| (hCol > 0 && hCol < 8 && h-hright1>=3 && h-hleft1>=3))
return 1;
else if (hCol == 0 && h == hright1 && h == hright2)
return 18;
else if (hCol == 6 && h == hright1 && h == hright2)
return 12;
else if (hCol < 6 && h == hright1 && h == hright2)
return 2;
else if (h == hright1)
{
if ((h-hright2 ==1) && ((hCol < 7 && h-hleft1 >= 2) || hCol ==7))
return 6;
else if ((h-hleft1 == 1) && ((hCol > 1 && h-hright2 >= 2) || hCol ==1))
return 8;
else
return 10;
}
else if ((hCol == 1 && h-hleft1==1)||(hCol > 1 && h-hleft1==1 && h-hleft2==2))
return 7;
else if ((hCol == 7 && h-hright1==1)||(hCol < 7 && h-hright1==1 && h-hright2==2))
return 9;
else if (hCol > 1 && h-hleft1==1 && h-hleft2==1)
return 16;
else if (hCol < 7 && h-hright1==1 && h-hright2==1)
return 14;
else if (hCol > 0 && h-hleft1==2)
return 13;
else if (hCol < 8 && h-hright1==2)
return 17;
else if (hCol > 0 && hCol < 8 && h-hright1==1 && h-hleft1==1)
return 4;
else if (hCol > 0 && h-hleft1==1)
return 3;
else if (hCol < 8 && h-hright1==1)
return 5;
}
void Diamond::GetShape(int choice, int hCol)
{
switch (choice)
{
case 0: Shape0(hCol);
break;
case 1: Shape1(hCol);
break;
case 2: Shape2(hCol);
break;
case 3: Shape3(hCol);
break;
case 4: Shape4(hCol);
break;
case 5: Shape5(hCol);
break;
case 6: Shape6(hCol);
break;
case 7: Shape7(hCol);
break;
case 8: Shape8(hCol);
break;
case 9: Shape9(hCol);
break;
case 10: Shape10(hCol);
break;
case 12: Shape12(hCol);
break;
case 13: Shape13(hCol);
break;
case 14: Shape14(hCol);
break;
case 16: Shape16(hCol);
break;
case 17: Shape17(hCol);
break;
case 18: Shape18(hCol);
break;
default: break;
}
}
void Diamond::Shape0(int hCol)
{
// ****
// 0000
// 0000
map[MaxRow-1][hCol] = '*';
map[MaxRow-1][hCol+1] = '*';
map[MaxRow-1][hCol+2] = '*';
map[MaxRow-1][hCol+3] = '*'; // PrintMap(); getchar();
int h = GetHeight(MaxRow-2, hCol);
for (int i=0; i<4; i++)
MovePart(MaxRow-2, hCol+i, h);
}
void Diamond::Shape1(int hCol)
{
// *000
// *000
// *000
// *000
map[MaxRow-1][hCol] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-3][hCol] = '*';
map[MaxRow-4][hCol] = '*';
int h = GetHeight(MaxRow-5, hCol); // cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-5, hCol, h);
}
void Diamond::Shape2(int hCol)
{
// 0*00
// ***0
// 0000
map[MaxRow-1][hCol+1] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-2][hCol+1] = '*';
map[MaxRow-2][hCol+2] = '*';
int h = GetHeight(MaxRow-3, hCol); //cout << h <<endl;PrintMap(); getchar();
for (int i=0; i<3; i++)
MovePart(MaxRow-3, hCol+i, h);
}
void Diamond::Shape3(int hCol)
{
// 0*00
// **00
// 0*00
map[MaxRow-1][hCol] = '*';
map[MaxRow-2][hCol-1] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-3][hCol] = '*';
int h = GetHeight(MaxRow-4, hCol); // cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-3, hCol-1, h);
MovePart(MaxRow-4, hCol, h);
}
void Diamond::Shape4(int hCol)
{
// ***0
// 0*00
// 0000
map[MaxRow-1][hCol-1] = '*';
map[MaxRow-1][hCol] = '*';
map[MaxRow-1][hCol+1] = '*';
map[MaxRow-2][hCol] = '*';
int h = GetHeight(MaxRow-3, hCol); // cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-2, hCol-1, h);
MovePart(MaxRow-3, hCol, h);
MovePart(MaxRow-2, hCol+1, h);
}
void Diamond::Shape5(int hCol)
{
// *000
// **00
// *000
map[MaxRow-1][hCol] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-2][hCol+1] = '*';
map[MaxRow-3][hCol] = '*';
int h = GetHeight(MaxRow-4, hCol); // cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-4, hCol, h);
MovePart(MaxRow-3, hCol+1, h);
}
void Diamond::Shape6(int hCol)
{
// 0**0
// **00
// 0000
map[MaxRow-1][hCol+1] = '*';
map[MaxRow-1][hCol+2] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-2][hCol+1] = '*';
int h = GetHeight(MaxRow-3, hCol); // cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-3, hCol, h);
MovePart(MaxRow-3, hCol+1, h);
MovePart(MaxRow-2, hCol+2, h);
}
void Diamond::Shape7(int hCol)
{
// *000
// **00
// 0*00
map[MaxRow-1][hCol-1] = '*';
map[MaxRow-2][hCol-1] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-3][hCol] = '*';
int h = GetHeight(MaxRow-4, hCol); // cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-3, hCol-1, h);
MovePart(MaxRow-4, hCol, h);
}
void Diamond::Shape8(int hCol)
{
// **00
// 0**0
// 0000
map[MaxRow-1][hCol-1] = '*';
map[MaxRow-1][hCol] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-2][hCol+1] = '*';
int h = GetHeight(MaxRow-3, hCol); // cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-2, hCol-1, h);
MovePart(MaxRow-3, hCol, h);
MovePart(MaxRow-3, hCol+1, h);
}
void Diamond::Shape9(int hCol)
{
// 0*00
// **00
// *000
map[MaxRow-1][hCol+1] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-2][hCol+1] = '*';
map[MaxRow-3][hCol] = '*';
int h = GetHeight(MaxRow-4, hCol); // cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-4, hCol, h);
MovePart(MaxRow-3, hCol+1, h);
}
void Diamond::Shape10(int hCol)
{
// **00
// **00
// 0000
map[MaxRow-1][hCol] = '*';
map[MaxRow-1][hCol+1] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-2][hCol+1] = '*';
int h = GetHeight(MaxRow-3, hCol); // cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-3, hCol, h);
MovePart(MaxRow-3, hCol+1, h);
}
void Diamond::Shape12(int hCol)
{
// 00*0
// ***0
// 0000
map[MaxRow-1][hCol+2] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-2][hCol+1] = '*';
map[MaxRow-2][hCol+2] = '*';
int h = GetHeight(MaxRow-3, hCol); // cout << h <<endl;PrintMap(); getchar();
for (int i=0; i<3; i++)
MovePart(MaxRow-3, hCol+i, h);
}
void Diamond::Shape13(int hCol)
{
// **00
// 0*00
// 0*00
map[MaxRow-1][hCol-1] = '*';
map[MaxRow-1][hCol] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-3][hCol] = '*';
int h = GetHeight(MaxRow-4, hCol); // cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-2, hCol-1, h);
MovePart(MaxRow-4, hCol, h);
}
void Diamond::Shape14(int hCol)
{
// ***0
// *000
// 0000
map[MaxRow-1][hCol] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-1][hCol+1] = '*';
map[MaxRow-1][hCol+2] = '*';
int h = GetHeight(MaxRow-3, hCol); // cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-3, hCol, h);
MovePart(MaxRow-2, hCol+1, h);
MovePart(MaxRow-2, hCol+2, h);
}
void Diamond::Shape16(int hCol)
{
// ***0
// 00*0
// 0000
map[MaxRow-1][hCol-2] = '*';
map[MaxRow-1][hCol-1] = '*';
map[MaxRow-1][hCol] = '*';
map[MaxRow-2][hCol] = '*';
int h = GetHeight(MaxRow-3, hCol); // cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-2, hCol-2, h);
MovePart(MaxRow-2, hCol-1, h);
MovePart(MaxRow-3, hCol, h);
}
void Diamond::Shape17(int hCol)
{
// **00
// *000
// *000
map[MaxRow-1][hCol] = '*';
map[MaxRow-1][hCol+1] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-3][hCol] = '*';
int h = GetHeight(MaxRow-4, hCol);// cout << h <<endl;PrintMap(); getchar();
MovePart(MaxRow-4, hCol, h);
MovePart(MaxRow-2, hCol+1, h);
}
void Diamond::Shape18(int hCol)
{
// *000
// ***0
// 0000
map[MaxRow-1][hCol] = '*';
map[MaxRow-2][hCol] = '*';
map[MaxRow-2][hCol+1] = '*';
map[MaxRow-2][hCol+2] = '*';
int h = GetHeight(MaxRow-3, hCol); //cout << h <<endl;PrintMap(); getchar();
for (int i=0; i<3; i++)
MovePart(MaxRow-3, hCol+i, h);
}
///////////////////////////////////////////////////////////////////////
int Calc(const char map[][MaxCol], int outCmd[][2]);
void PrintMap(const char map[][MaxCol]); //打印传入的地图
void PrintOutCmd(const int outCmd[][2], int n); //打印输出方案，即选择的模块信息
int GetMin(const int a[], int len);//选择所需的模块数量较少的数据
int Project(const char map[][MaxCol], int out[][1000][2], int n);
int ChangeCol(int choice, int hCol); //转换列号，以满足题目要求（原来是存储的列号
//是地图中具有最大高度的列号，现改为所选模块的最左侧有效方块放到地图中所在的列）
int main()
{
char map[MaxRow][MaxCol] = {
'0','0','*','0','0','0','0','0','*',
'*','*','*','0','*','*','*','*','*',
'0','*','0','*','0','*','0','*','0',
'*','0','*','*','*','0','*','0','*',
'0','*','*','0','*','0','0','*','*',
'0','0','0','0','*','*','*','0','0',
'*','*','0','*','*','*','0','*','*',
'0','0','0','0','*','0','*','0','0',
'*','*','0','*','0','*','0','*','*',
'0','0','0','*','0','0','0','0','0',
'0','0','0','0','0','0','0','0','0',
'0','0','0','0','0','0','0','0','0',
'0','0','0','0','0','0','0','0','0',
'0','0','0','0','0','0','0','0','0',
'0','0','0','0','0','0','0','0','0',
'0','0','0','0','0','0','0','0','0',
'0','0','0','0','0','0','0','0','0',
'0','0','0','0','0','0','0','0','0',
'0','0','0','0','0','0','0','0','0',
'0','0','0','0','0','0','0','0','0'};
int outCmd[1000][2] = {0};
PrintMap(map); getchar();
int n = Calc(map, outCmd);
cout << "\nn = " << n << endl;
if (n > 0)
PrintOutCmd(outCmd, n);
getchar();
return 0;
}
int Calc(const char map[][MaxCol], int outCmd[][2])
{
int out[4][1000][2] = {0}; //根据设置的第1种优先权操作
int min[4] = {1000, 1000, 1000, 1000};//用来保存第1-4套方案所需的模块数量
//因为4套方案各有所长，故依次先后运行，取较好的数据
for (int i=0; i<4; i++)
{
min[i] = Project(map, out, i);
}
switch (GetMin(min, 4))
{
case 0: if (min[0] > 999)
min[0] = -1;
for (int i=0; i<min[0]; i++)
{
outCmd[i][0] = out[0][i][0];
outCmd[i][1] = ChangeCol(out[0][i][0], out[0][i][1]);
}
return min[0];
case 1: if (min[1] > 999)
min[1] = -1;
for (int i=0; i<min[1]; i++)
{
outCmd[i][0] = out[1][i][0];
outCmd[i][1] = ChangeCol(out[1][i][0], out[1][i][1]);
}
return min[1];
case 2: if (min[2] > 999)
min[2] = -1;
for (int i=0; i<min[2]; i++)
{
outCmd[i][0] = out[2][i][0];
outCmd[i][1] = ChangeCol(out[2][i][0], out[2][i][1]);
}
return min[2];
case 3: if (min[3] > 999)
min[3] = -1;
for (int i=0; i<min[3]; i++)
{
outCmd[i][0] = out[3][i][0];
outCmd[i][1] = ChangeCol(out[3][i][0], out[3][i][1]);
}
return min[3];
}
}
int Project(const char map[][MaxCol], int out[][1000][2], int n)
{
Diamond my(map); //创建对象
int count = 0; //累积添加模块数
int choice;
while (0 != my.Check())
{
int highestCol = my.GetHighestCol(); //读取具有最大高度的列号
switch (n)
{
case 0: choice = my.Choose1(highestCol); //按照第1套方案选择所需的模块
break;
case 1: choice = my.Choose2(highestCol); //按照第2套方案选择所需的模块
break;
case 2: choice = my.Choose3(highestCol); //按照第3套方案选择所需的模块
break;
case 3: choice = my.Choose4(highestCol); //按照第4套方案选择所需的模块
break;
}
my.GetShape(choice, highestCol); //操作所选的模块
out[n][count][0] = choice;
out[n][count][1] = highestCol;
count++;
if (count > 999)
break;
}
return count;
}
int GetMin(const int a[], int len)
{
int min = 0;
for (int i=1; i<len; i++)
{
if (a[min] > a[i])
min = i;
}
return min;
}
void PrintMap(const char map[][MaxCol])
{
for (int i=MaxRow-1; i>=0; i--)
{
for (int j=0; j<MaxCol; j++)
cout << map[i][j];
cout << "\n";
}
}
void PrintOutCmd(const int outCmd[][2], int n)
{
for (int i=0; i<n; i++)
cout << outCmd[i][0] << " - " << outCmd[i][1] << "\t";
}
int ChangeCol(int choice, int hCol)
{
switch (choice)
{
case 0: return hCol;
case 1: return hCol;
case 2: return hCol;
case 3: return hCol - 1;
case 4: return hCol - 1;
case 5: return hCol;
case 6: return hCol;
case 7: return hCol - 1;
case 8: return hCol;
case 9: return hCol;
case 10: return hCol;
case 12: return hCol;
case 13: return hCol - 1;
case 14: return hCol;
case 16: return hCol - 2;
case 17: return hCol;
case 18: return hCol;
default: cout << "ERROR!\n";
return -1;
}
}
评论