玄学。。。
放代码：
#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;

int N;
#define H 10
#define W 15

char board[H][W];
char buf[20];

int dy[4] = { 0, -1, 0, 1 };
int dx[4] = { -1, 0, 1, 0 };

queue<pair<int, int> > que;

#define in_board(y,x) (y >= 0 && y < H && x >= 0 && x < W)

bool is_end(int& num)
{
	num = 0;
	
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			if (board[i][j] == 'R' || board[i][j] == 'G' || board[i][j] == 'B')
			{
				num++;
				for (int k = 0; k < 4; k++)
				{
					if (in_board(i + dy[k], j + dx[k]))
					{
						if (board[i + dy[k]][j + dx[k]] == board[i][j])
						{
							return false;
						}
					}
				}
			}
		}
	}
	return true;
}

void align()
{
	for (int j = 0; j < W; j++)
	{
		int cnt = 0;
		int bcnt = 0;
		for (int i = 0; i < H; i++)
		{
			if (board[i][j] == 'R' || board[i][j] == 'G' || board[i][j] == 'B')
			{
				cnt++;
			}
			else 
			{
				if (cnt)
				{
					for (int l = 0; l < cnt; l++)
					{
						board[i - l][j] = board[i - l - 1][j];
					}
					board[i - cnt][j] = ' ';
				}
			}
		}
	}
	int cnt = 0;
	for (int j = W - 1; j >= 0; j--)
	{
		if (board[H - 1][j] == 'R' || board[H - 1][j] == 'G' || board[H - 1][j] == 'B')
		{
			cnt++;
		}
		else
		{
			if (cnt)
			{
				for (int l = 0; l < cnt; l++)
				{
					for (int i = 0; i < H; i++)
					{
						board[i][j + l] = board[i][j + l + 1];
					}
				}
				for (int i = 0; i < H; i++)
				{
					board[i][j + cnt] = ' ';
				}
			}
		}
	}
	
	return;
}

int bfs(int y, int x, char c, int& leftmost, int& lowermost)
{
	int cnt = 0;

	board[y][x] = ' ';

	leftmost = x;
	lowermost = y;

	que.push(make_pair(y, x));

	while (!que.empty())
	{
		cnt++;
		pair<int, int> cur = que.front();
		que.pop();

		for (int i = 0; i < 4; i++)
		{
			int tmpy = cur.first + dy[i];
			int tmpx = cur.second + dx[i];
			if (in_board(tmpy, tmpx))
			{
				if (board[tmpy][tmpx] == c)
				{
					if (tmpx < leftmost)
					{
						leftmost = tmpx;
						lowermost = tmpy;
					}
					else if (tmpx == leftmost)
					{
						if (tmpy > lowermost)
						{
							lowermost = tmpy;
						}
					}
					board[tmpy][tmpx] = ' ';

					que.push(make_pair(tmpy, tmpx));
				}
			}
		}
	}
	return cnt;
}
void solve(int step, int score)
{
	int tmp_board[H][W];
	bool tmp_mark[H][W];
	int max_num = 0;
	int y = 0, x = 0;
	int num_remain;

	if (is_end(num_remain))
	{
		if (num_remain == 0)
		{
			score += 1000; 
		}
		printf("Final score: %d, with %d balls remaining.\n\n",
			score, num_remain);
		return;
	}
	
	memcpy(tmp_board, board, H*W);

	for (int i = H-1; i >= 0; i--)
	{
		for (int j = 0; j < W; j++)
		{
			if (board[i][j] == 'R' || board[i][j] == 'G' || board[i][j] == 'B')
			{
				for (int k = 0; k < 4; k++)
				{
					if (in_board(i + dy[k], j + dx[k]) 
						&& board[i + dy[k]][j + dx[k]]  == board[i][j]
						)
					{
						int loc_y = i;
						int loc_x = j;
						int num = bfs(i, j, board[i][j], loc_x, loc_y);
						if (num > max_num)
						{
							y = loc_y;
							x = loc_x;
							max_num = num;
						}
						else if (num == max_num)
						{
							if (loc_x < x)
							{
								x = loc_x;
								y = loc_y;
							}
							else if (loc_x == x)
							{
								if (loc_y > y)
								{
									y = loc_y;
								}
							}
						}
						
						break;
					}
				}
			}
		}
	}
	int a, b;
	memcpy(board, tmp_board, H*W);
	
	printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n",
		step, H - y, x+1, max_num, board[y][x], (max_num - 2)*(max_num - 2));
	
	bfs(y, x, board[y][x],a,b);
	
	align();
	
	solve(step+1, (max_num - 2)*(max_num - 2)+score);
	return;
}
int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		for (int i = 0; i < H; i++)
		{
			scanf("%s", buf);
			for (int j = 0; j < W; j++)
			{
				board[i][j] = buf[j];
			}
		}
		printf("Game %d:\n\n", i);

		solve(1, 0);
	}
}

• Re:局部queue TLE，改成全局queue就变成235ms (31) 1716143223 2019-04-14 13:20:15