| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
ac,贴代码,将16行vector改成 [] 后解决Memory Limit Exceed#include <iostream>
#include <string>
using namespace std;
struct P{
int r,c;
P(int row,int col){
r=row;c=col;
}
P(){
r=-1;c=-1;
}
};
char board[10][15];
int cnts[10][15]={0};
P v[150];
void reset_cnts(){
for(int i=0;i<10;i++){
for(int j=0;j<15;j++){
cnts[i][j]=0;
}
}
}
void stat_cnts(){
for(int r=0;r<10;r++){
for(int c=0;c<15;c++){
if(cnts[r][c] > 0 || board[r][c] == ' '){
continue;
}
int front = 0;
int cnt=1;
v[front] = P(r,c);
cnts[r][c]=1;
while(cnt - front > 0){
P p = v[front];
if(p.c<14 && board[p.r][p.c]==board[p.r][p.c+1] && cnts[p.r][p.c+1]==0){
v[cnt]=P(p.r,p.c+1);
cnt++;
cnts[p.r][p.c+1]=1;
}
if(p.r<9 && board[p.r][p.c]==board[p.r+1][p.c] && cnts[p.r+1][p.c]==0){
v[cnt]=P(p.r+1,p.c);
cnt++;
cnts[p.r+1][p.c]=1;
}
if(p.c>0 && board[p.r][p.c]==board[p.r][p.c-1] && cnts[p.r][p.c-1]==0){
v[cnt]=P(p.r,p.c-1);
cnt++;
cnts[p.r][p.c-1]=1;
}
if(p.r>0 && board[p.r][p.c]==board[p.r-1][p.c] && cnts[p.r-1][p.c]==0){
v[cnt]=P(p.r-1,p.c);
cnt++;
cnts[p.r-1][p.c]=1;
}
front++;
}
for(int i=0;i<cnt;i++){
P p = v[i];
cnts[p.r][p.c]=cnt;
}
}
}
}
void find_largest_cluster(int &row, int &col, int &cnt){
int l = -1;
for(int c=0;c<15;c++){
for(int r=0;r<10;r++){
if(cnts[r][c] > 1 && cnts[r][c] > l){
row = r;
col = c;
l = cnts[r][c];
cnt = l;
}
}
}
}
void copy_col(int from, int to){
for(int r=0;r<10;r++){
if(board[r][from]!=' '){
board[r][to] = board[r][from];
board[r][from]=' ';
}else{
break;
}
}
}
void move_by_index(int r, int c){
if(r<0 || r>9 || c<0 || c>14){
return;
}
// remove cluster
char color = board[r][c];
int front = 0;
int cnt=1;
v[front]=P(r,c);
board[r][c] = ' ';
while(cnt - front > 0){
P p = v[front];
if(p.c<14 && color==board[p.r][p.c+1]){
v[cnt]=P(p.r,p.c+1);
board[p.r][p.c+1] = ' ';
cnt++;
}
if(p.r<9 && color==board[p.r+1][p.c]){
v[cnt]=P(p.r+1,p.c);
board[p.r+1][p.c] = ' ';
cnt++;
}
if(p.c>0 && color==board[p.r][p.c-1]){
v[cnt]=P(p.r,p.c-1);
board[p.r][p.c-1] = ' ';
cnt++;
}
if(p.r>0 && color==board[p.r-1][p.c]){
v[cnt]=P(p.r-1,p.c);
board[p.r-1][p.c] = ' ';
cnt++;
}
front++;
}
//down
for(int c=0;c<15;c++){
int to_index=0;
while(to_index<10 && board[to_index][c] != ' '){
to_index++;
}
if(to_index>9){
continue;
}
int from_index=to_index;
while(from_index<10 && board[from_index][c] == ' '){
from_index++;
}
if(from_index>9){
continue;
}
while(to_index<10 && from_index<10){
board[to_index][c] = board[from_index][c];
board[from_index][c]=' ';
to_index++;
while(from_index<10 && board[from_index][c] == ' '){
from_index++;
}
}
}
//left
int to_c_index=0;
while(to_c_index<15 && board[0][to_c_index] != ' '){
to_c_index++;
}
if(to_c_index>14){
return;
}
int from_c_index=to_c_index;
while(from_c_index<15 && board[0][from_c_index] == ' '){
from_c_index++;
}
if(from_c_index > 14){
return;
}
while(to_c_index<15 && from_c_index<15){
copy_col(from_c_index,to_c_index);
to_c_index++;
while(from_c_index<15 && board[0][from_c_index] == ' '){
from_c_index++;
}
}
}
int cnt_board_ball(){
int cnt = 0;
for(int c=0;c<15;c++){
if(board[0][c] == ' '){
break;
}
for(int r=0;r<10;r++){
if(board[r][c] == ' '){
break;
}
cnt++;
}
}
return cnt;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
string row;
for(int r=9;r>=0;r--){
cin>>row;
for(int c=0;c<15;c++){
board[r][c]=row[c];
}
}
cout<<"Game "<<i+1<<":"<<endl<<endl;
int move = 1;
int score = 0;
while(true){
reset_cnts();
stat_cnts();
int lr=-1,lc=-1,l=0;
find_largest_cluster(lr,lc,l);
if(lr != -1){
char color = board[lr][lc];
int cur_s=(l-2)*(l-2);
cout<<"Move "<<move<<" at ("<<lr+1<<","<<lc+1<<"): removed "<<l<<" balls of color "<<color<<", got "<<cur_s<<" points."<<endl;
move_by_index(lr,lc);
score+=cur_s;
move++;
}else{
int remain = cnt_board_ball();
if(remain == 0){
score += 1000;
}
cout<<"Final score: "<<score<<", with "<<remain<<" balls remaining."<<endl<<endl;
break;
}
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator