programming.txt

一个俄罗斯方块的外挂程序 不过不全,但可以参考以下程序

*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。可以打印任意时刻的地图，以观察变化情况。 
*/ 
#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);//按照优先顺序选择对应的模块，返回模块的编号 
 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 Shape8(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;
}


void Diamond::GetShape(int choice, int hCol)
{