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