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

ac,贴代码,将16行vector改成 [] 后解决Memory Limit Exceed

Posted by liduoldbiubiubiu at 2020-01-15 18:07:23 on Problem 1027
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator