本文共 5566 字，大约阅读时间需要 18 分钟。

题意：在一个固定大小为10x15的矩形区域A内被RGB三种颜色的小球填满，每次可以选择同种颜色（上下左右）连通小球数>=2的区域进行删除，删除后，上方的小球会下落，如果有空列，将其右边的列进行整列左移，移动后小球的相对顺序不变。设m(m>=2)为删除个数，每次的得分为(m-2)*(m-2)，如果最后所有的小球全部能够删除，奖励1000分。当区域A没有剩余小球或是最大连通区域的小球个数为1时游戏结束。现每步删除最大的连通区域，如果存在多个相同的最大连通区域，选择最左最下的小球所在的连通区域，输出每步得分和总得分。

 

算法：模拟，寻找最大连通区域时可用dfs或bfs

#include 
   
    #include 
    
     using namespace std;char map[11][26];int dir[4][2] = {
  {1, 0}, {-1, 0}, {0, 1}, {0, -1}};  bool vis[11][16];int cnt;int curr_row,curr_col;bool inMap(int row, int col){	return (row>=0 && row<10 && col>=0 && col<15);}// 计算最大连通区域 void dfs(int row, int col){	vis[row][col] = true;	cnt++;	for (int i=0; i<4; i++)	{		int nr = row + dir[i][0];		int nc = col + dir[i][1];		if (inMap(nr,nc) && !vis[nr][nc] && map[nr][nc]==map[row][col])		{			dfs(nr,nc);		}	}}void remove(int row, int col){	char c = map[row][col];	map[row][col] = ' ';	for (int i=0; i<4; i++)	{		int nr = row + dir[i][0];		int nc = col + dir[i][1];		if (inMap(nr,nc) && map[nr][nc]==c)		{			remove(nr,nc);		}	}}int chooseBall(){	memset(vis,false,sizeof(vis));	int num = -1;	int row,col;	// 从左下角开始选 	for (int i=0; i<15; i++)	{		for (int j=0; j<10; j++)		{			if (map[j][i] == ' ' || vis[j][i])			{				continue;			}			cnt = 0;			dfs(j,i);			if (cnt > num)			{				num = cnt;				curr_row = j;				curr_col = i;			}		}	}	return num;}// 小球落下+非空行左移 void fresh(){	int i,j,k;	bool isEmpty[20];		// isEmpty[i]=true：第i列为空 	memset(isEmpty,false,sizeof(isEmpty));	for (i=0; i<15; i++)	{		// 找每一列的第一个非空元素 		int ballNum = -1;		for (j=0; j<10; j++)		{			if (map[j][i] != ' ')			{				map[++ballNum][i] = map[j][i];			}		}		// 如果是空行 		if (ballNum == -1)		{			isEmpty[i] = true;			continue;		}		// 小球落下 		for (k=ballNum+1; k<10; k++)		{			map[k][i] = ' ';		}	}	// 非空行左移 	for (i=0; i<15; i++)	{		if (isEmpty[i])		{			for (j=i+1; j<15; j++)			{				if (!isEmpty[j])				{					break; 				}			}			if (j >= 15)			{				break;			}			isEmpty[j] = true;			isEmpty[i] = false;			for (k=0; k<10; k++)			{				map[k][i] = map[k][j];				map[k][j] = ' ';			}		}	}}int main(){	int cases;	cin >> cases;	for (int i=1; i<=cases; i++)	{		for (int j=9; j>=0; j--)		{			cin >> map[j];		}		cout << "Game " << i << ":" << endl << endl;		int steps = 1;		int score = 0;		int ballNum;		int leftBallNum=150;		while (true)		{			ballNum = chooseBall();			if (ballNum == -1)			{				score += 1000;				break;			}			else if (ballNum == 1)			{				break;			}			leftBallNum -= ballNum;			cout << "Move " << steps++ << " at (" << curr_row+1 << "," << curr_col+1 << "): removed " << ballNum 			<< " balls of color " << map[curr_row][curr_col] << ", got " << (ballNum-2)*(ballNum-2) << " points." << endl;						score += (ballNum-2) * (ballNum-2);			remove(curr_row,curr_col);			fresh();		}		cout << "Final score: " << score << ", with " << leftBallNum << " balls remaining. " << endl << endl;	}}
    
   

 

#include 
   
    #include 
    
     #include 
     
      using namespace std;char map[11][26];int dir[4][2] = {
  {1, 0}, {-1, 0}, {0, 1}, {0, -1}};  bool vis[11][16];int cnt;int curr_row,curr_col; bool inMap(int row, int col){	return (row>=0 && row<10 && col>=0 && col<15);}// 计算最大连通区域 void bfs(int row, int col){	int q[160];	int tail,head;	tail = head = 0;	int loc = row * 15 + col;	vis[row][col] = true;	q[tail++] = loc;	while(head < tail)	{		loc = q[head++];		cnt++;		for (int i=0; i<4; i++)		{			int nr = loc/15 + dir[i][0];			int nc = loc%15 + dir[i][1];			if (inMap(nr,nc) && !vis[nr][nc] &&  map[nr][nc]==map[row][col])			{				vis[nr][nc] = true;				q[tail++] = nr*15+nc;			}		}	}}// 将从(row,col)开始的连通区域置为空 void remove(int row, int col){	char c = map[row][col];	map[row][col] = ' ';	for (int i=0; i<4; i++)	{		int nr = row + dir[i][0];		int nc = col + dir[i][1];		if (inMap(nr,nc) && map[nr][nc]==c)		{			remove(nr,nc);		}	}}int chooseBall(){	memset(vis,false,sizeof(vis));	int num = -1;	int row,col;	// 最左，最下 	for (int i=0; i<15; i++)	{		for (int j=0; j<10; j++)		{			if (map[j][i] == ' ' || vis[j][i])			{				continue;			}			cnt = 0;			bfs(j,i);			if (cnt > num)			{				num = cnt;				curr_row = j;				curr_col = i;			}		}	}	return num;}// 小球落下+非空行左移 void fresh(){	int i,j,k;	bool isEmpty[20];		// isEmpty[i]=true：第i列为空 	memset(isEmpty,false,sizeof(isEmpty));	for (i=0; i<15; i++)	{		// 找每一列的第一个非空元素 		int ballNum = -1;		for (j=0; j<10; j++)		{			if (map[j][i] != ' ')			{				map[++ballNum][i] = map[j][i];			}		}		// 如果是空行 		if (ballNum == -1)		{			isEmpty[i] = true;			continue;		}		// 小球落下 		for (k=ballNum+1; k<10; k++)		{			map[k][i] = ' ';		}	}	// 非空行左移 	for (i=0; i<15; i++)	{		if (isEmpty[i])		{			for (j=i+1; j<15; j++)			{				if (!isEmpty[j])				{					break; 				}			}			if (j >= 15)			{				break;			}			isEmpty[j] = true;			isEmpty[i] = false;			for (k=0; k<10; k++)			{				map[k][i] = map[k][j];				map[k][j] = ' ';			}		}	}}int main(){	int cases;	cin >> cases;	for (int i=1; i<=cases; i++)	{		for (int j=9; j>=0; j--)		{			cin >> map[j];		}		cout << "Game " << i << ":" << endl << endl;		int steps = 1;		int score = 0;		int ballNum;		int leftBallNum=150;		while (true)		{			ballNum = chooseBall();			if (ballNum == -1)			{				score += 1000;				break;			}			else if (ballNum == 1)			{				break;			}			leftBallNum -= ballNum;			cout << "Move " << steps++ << " at (" << curr_row+1 << "," << curr_col+1 << "): removed " << ballNum << 			" balls of color " << map[curr_row][curr_col] << ", got " << (ballNum-2)*(ballNum-2) << " points." << endl;						score += (ballNum-2) * (ballNum-2);			remove(curr_row,curr_col);			fresh();		}		cout << "Final score: " << score << ", with " << leftBallNum << " balls remaining. " << endl << endl;	}}