Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

局部queue TLE，改成全局queue就变成235ms

Posted by 1500012922 at 2018-07-28 21:13:24 on Problem 1027
```玄学。。。

#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);
}
}```

Followed by: