第18次比赛第2题程序 -- 业余空间-- 编程爱好者博客

/*iAkiak热衷于网络俄罗斯方块对战游戏。为了能够赢得更多的比赛，他决定编写一个俄罗斯方块的外挂程序。他希望这个程序能够尽快的把游戏中所有的方块消除。虽然俄罗斯方块游戏几乎耳熟能详、人尽皆知，但为了让大家明确，还是先介绍一下：俄罗斯方块游戏内有19种不同的4*4的方块组合。每种组合都只有4个连续的有效方块（用*表示），其余部分是空白方块（用0表示）。有的方块仅仅是其他方块旋转得到的。下面列举出所有19种方块，为了便于讨论，给它们依次编号0..18： **** *0000000 *0000000 *0000000 *000(0) (1) 0*00 0*00 ***0 *000***0 **00 0*00 **000000 0*00 0000 *0000000 0000 0000 0000(2) (3) (4) (5) 0**0 *000 **00 0*00**00 **00 0**0 **000000 0*00 0000 *0000000 0000 0000 0000(6) (7) (8) (9) **00**0000000000(10) *000 00*0 **00 ***0*000 ***0 0*00 *000**00 0000 0*00 00000000 0000 0000 0000(11) (12) (13) (14) 0*00 ***0 **00 *0000*00 00*0 *000 ***0**00 0000 *000 00000000 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; } }

博客介绍

正文

第18次比赛第2题程序2006-03-05 12:01:00

评论