問題：
讓電腦自動下俄羅斯方塊游戲。
解法：
對當前的積木塊，枚舉它旋轉後的每一個形狀從每一列落下的棋盤，將該棋盤和前一個棋盤進行對比，並打分，最後取得分最高的那個形狀和那一列作為電腦的當前操作。（鑒於有讀者不會用這個程序，在此說明下，運行這個程序需要加上文件重定向<1_17.txt，或者把程序中的控制台輸入scanf改成文件輸入FILE* fin=fopen("1_17.txt"); fscanf(fin,"%d",...);）
[cpp]
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
// 積木塊的信息
#define BLOCK_SIZE 7
#define ROTATE_SIZE 4
#define SIDE_LEN 4
const int BLOCK_AREA = SIDE_LEN*SIDE_LEN;
// 棋盤的信息
#define HORIZ_LEN 12
#define VERT_LEN 15
const int CHESS_AREA = HORIZ_LEN*VERT_LEN;
// 其它信息
#define TOP_STEP 25
#define inf 10000
// 計分信息
const int clearLineScore[] = {0, 1, 3, 7, 13};
struct Block // 積木塊
{
void init(unsigned char *l)
{
memcpy(layout, l, BLOCK_AREA);
int i, j;
for (i=0; i<SIDE_LEN; i++)
{
for (j=SIDE_LEN-1; j>=0 && layout[j*SIDE_LEN+i]==0; j--);
maxRow[i] = j+1;
}
for(i=0; i<SIDE_LEN && maxRow[i]==0; i++);
minCol = i;
for (i=SIDE_LEN-1; i>=0 && maxRow[i]==0; i--);
maxCol = i;
}
unsigned char layout[BLOCK_AREA]; // 積木塊的布局
unsigned char maxRow[SIDE_LEN]; // 積木塊每一列所占區域的最大行，取值從1開始
unsigned char minCol; // 積木塊所占區域的最小值列和最大列，取值從0開始
unsigned char maxCol;
};
Block blockSet[BLOCK_SIZE][ROTATE_SIZE]; // 7種積木塊，每種積木塊有4種旋轉方向
unsigned char chess[CHESS_AREA]; // 棋盤的布局
unsigned char nextChess[CHESS_AREA]; // 下一步棋盤的布局
int height[HORIZ_LEN]; // 棋盤每一列所占區域的最小行，即高度
void calcHeight(unsigned char *curchess) // 計算當前棋盤的高度信息
{
int i, j;
for (i=0; i<HORIZ_LEN; i++)
{
for (j=0; j<VERT_LEN && curchess[j*HORIZ_LEN+i]==0; j++);
height[i] = j;
}
}
// 計算若積木塊從offsetX列落下，會落在第幾行，即offsetY
int calcBottomOffsetY(const Block& b, int offsetX)
{
int offsetY = VERT_LEN;
for (int i=0; i<SIDE_LEN; i++)
{
if (b.maxRow[i]==0) continue;
offsetY = min(offsetY, height[offsetX+i]-b.maxRow[i]);
}
return offsetY;
}
// 將積木塊貼到棋盤上
void pasteTo(unsigned char *curchess, const Block& b,
int offsetX, int offsetY)
{
for (int i=b.minCol; i<=b.maxCol; i++)
for (int j=0; j<SIDE_LEN; j++)
{
unsigned char bij = b.layout[j*SIDE_LEN + i];
unsigned char& cij = curchess[(j+offsetY)*HORIZ_LEN + i+offsetX];
if (bij && cij==0)
cij = bij;
else if (bij && cij)
cout << "ERROR" << endl;
}
}
// 消去[offsetY,offsetY+SIDE_LEN)中remline為1的行
void clearLines(unsigned char *curchess, int offsetY, unsigned char *remline)
{
int i, j, gap=0;
for (j=offsetY+SIDE_LEN-1; j>=0; j--)
{
if (j-offsetY>=0 && remline[j-offsetY])
gap++;
else if (gap)
{
memcpy(curchess+(j+gap)*HORIZ_LEN, curchess+j*HORIZ_LEN, HORIZ_LEN);
}
}
}
// 計算[offsetX,offsetX+SIDE_LEN)列的洞的個數
int calcHoles(unsigned char *curchess, int offsetX, int offsetY)
{
int i, j;
int holeCount = 0;
for (i=offsetX; i<offsetX+SIDE_LEN; i++)
{
if (i<0 || i>=HORIZ_LEN) continue;
for (j=offsetY; j<VERT_LEN && curchess[j*HORIZ_LEN+i]==0; j++);
for (; j<VERT_LEN; j++)
if (curchess[j*HORIZ_LEN+i]==0)
holeCount++;
}
return holeCount;
}
// 計算當前棋盤的得分
int calcScore(unsigned char *curchess, int offsetX, int offsetY)
{
int i, j, score = 0;
int remlineCount = 0;
unsigned char remline[SIDE_LEN] = {0};
// 統計消行數
for (j=offsetY; j<offsetY+SIDE_LEN; j++)
{
for (i=0; i<HORIZ_LEN && curchess[j*HORIZ_LEN+i]; i++);
if (i==HORIZ_LEN)
{
remlineCount++;
remline[j-offsetY] = 1;
}
}
score += clearLineScore[remlineCount];
// 統計洞的個數
if (remlineCount)
clearLines(curchess, offsetY, remline);
int holeCount = calcHoles(curchess, offsetX, offsetY) -
calcHoles(chess, offsetX, offsetY);
score -= holeCount*4;
// 位置過高則扣分
if (holeCount > 5) score -= 15;
if (offsetY-remlineCount < VERT_LEN*3/5)
score -= VERT_LEN*3/5-(offsetY-remlineCount);
return score;
}
void output(unsigned char *curchess)
{
for (int j=0; j<VERT_LEN; j++)
{
for (int i=0; i<HORIZ_LEN; i++)
cout << curchess[j*HORIZ_LEN+i] << " ";
cout << endl;
}
}
int main()
{
srand(time(0));
int i, j, k, n, m;
// 初始化積木塊
for (i=0; i<BLOCK_SIZE; i++)
for (j=0; j<ROTATE_SIZE; j++)
{
unsigned char l[BLOCK_AREA];
for (k=0; k<BLOCK_AREA; k++)
scanf("%d",&l[k]);
blockSet[i][j].init(l);
}
// 初始化棋盤
for (i=0; i<CHESS_AREA; i++)
scanf("%d",&chess[i]);
// 顯示前TOP_STEP步
int offsetX, offsetY;
unsigned char tmpchess[CHESS_AREA];
for (n=TOP_STEP; n>=0; n--)
{
output(chess);
calcHeight(chess); // 為每一步計算一次height數組，避免計算offsetY時過多的重復計算
int bind = rand()%BLOCK_SIZE; // 積木塊的序號
int maxScore = -inf;
for (j=0; j<ROTATE_SIZE; j++) // 要考慮積木塊的各種旋轉情況
{
const Block& b = blockSet[bind][j]; // 得到當前的積木塊
for (offsetX=-b.minCol; offsetX<HORIZ_LEN-b.maxCol; offsetX++)
{
// 計算從offsetX列落下，所落在棋盤的位置offsetY
offsetY = calcBottomOffsetY(b, offsetX);
if (offsetY<0) continue;
memcpy(tmpchess, chess, CHESS_AREA);
pasteTo(tmpchess, b, offsetX, offsetY); // 在棋盤中添加積木塊
int curScore = calcScore(tmpchess, offsetX, offsetY); // 計算當前情況下的得分
if (curScore > maxScore)
{
maxScore = curScore; www.2cto.com
memcpy(nextChess, tmpchess, CHESS_AREA);
}
}
}
memcpy(chess, nextChess, CHESS_AREA);
}
}
