[BOJ] Puyo Puyo - 11559

51443 ワード
algorithm テキストリンク

📃 質問する


[BOJ] Puyo Puyo 🔗リンク


アクセス

  • 模擬問題なので、先に実施して最適化したい.
  • 実施ロジックは3段階に分けられる.(チェーンブロックをチェック→チェーンブロックを削除→落ちたブロックを移動)
  • チェーン店確認checkBlock():与えられたField(6 x 12)は小さく,DFSを用いて接続されたブロックを確認した.
  • ブロッククリアremoveBlock():接続されたブロックの座標をスタックで受信し、空白領域に初期化します.
  • 落下したブロックを移動moveBlock():どの要素もSHIFTはあまりにも非効率的だと感じています.
    各縦軸について、空白でないブロックを新しいアレイに挿入し、フィールドの各縦軸に代入します.
    これを容易にするために,横/縦入力を反転することによって実現した.

    • 🧠 に答える

    #include <iostream>
#include <cstring>
#include <stack>
#include <map>
#include <utility>

using namespace std;

int board[7][13] = {0,};
int visit[7][13] = {0,};
const int mapX = 6;
const int mapY = 12;
const int VISITED = 1;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
map<char, int> colorToNum = {{'.',0}, {'R',1}, {'G',2}, {'B',3}, {'P',4}, {'Y',5},};

stack<pair<int, int>> checkBlock(int x, int y);
bool isSafe(int x, int y);
void removeBlock(stack<pair<int,int>> *checkedBlock);
void moveBlock();

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    char block;
    for(int i=mapY-1; i>=0; i--){
        for(int j=0; j<mapX; j++){
            cin >> block;
            board[j][i] = colorToNum[block];
        }
    }
    
    int chain = -1;
    bool isChain;
    do{
        isChain = false;
        chain++;
        memset(visit, 0, sizeof(visit));
        
        for(int i=0; i<mapX; i++){
            for(int j=0; j<mapY; j++){
                if(board[i][j] && !visit[i][j]){
                    stack<pair<int,int>> checkedBlock = checkBlock(i, j);
                    
                    if(checkedBlock.size() >= 4){
                        isChain = true;
                        removeBlock(&checkedBlock);
                    }
                }
            }
        }
        
        moveBlock();
    }while(isChain);
    
    cout << chain << endl;
    
    return 0;
}

stack<pair<int, int>> checkBlock(int x, int y){
    stack<pair<int, int>> checkedBlock;
    checkedBlock.push(make_pair(x,y));
    
    stack<pair<int, int>> s;
    s.push(make_pair(x,y));
    visit[x][y] = VISITED;
    
    while(!s.empty()){
        int mx = s.top().first;
        int my = s.top().second;
        int mColor = board[mx][my];
        s.pop();
        
        for(int i=0; i<4; i++){
            int nx = mx + dx[i];
            int ny = my + dy[i];
            
            if(!isSafe(nx,ny) || visit[nx][ny] || board[nx][ny]!=mColor)  continue;
            
            visit[nx][ny] = VISITED;
            s.push(make_pair(nx,ny));
            checkedBlock.push(make_pair(nx,ny));
        }
    }
    
    return checkedBlock;
}

bool isSafe(int x, int y){
    return (x>=0 && x<mapX && y>=0 && y<mapY);
}

void removeBlock(stack<pair<int,int>> *checkedBlock){
    stack<pair<int,int>> s = *checkedBlock;
    while(!s.empty()){
        int mx = s.top().first;
        int my = s.top().second;
        s.pop();
        
        board[mx][my] = 0;
    }
}

void moveBlock(){
    for(int i=0; i<mapX; i++){
        int tmp[13] = {0,};
        int tmpIndex = 0;
        for(int j=0; j<mapY; j++){
            if(board[i][j]){
                tmp[tmpIndex++] = board[i][j];
            }
        }
        memcpy(board[i], tmp, sizeof(int) * 13);
    }
}

    🧠 解の最適化

  • 入力は文字で入力し、文字→整数置換部分を除いた.
  • DFSスタック使用部分を消去するように再表示する.
  • PointClassを作成してx、y座標を表します.
    • #include <iostream>
#include <cstring>
#include <vector>

using namespace std;

class Point {
public:
    int x,y;

    Point(int x, int y) {
        this->x = x;
        this->y = y;
    }
};

char board[7][13] = {0,};
int visit[7][13] = {0,};
const int mapX = 6;
const int mapY = 12;
const int VISITED = 1;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
vector<Point> checkedBlock;

void checkBlock(int x, int y, char block);
bool isSafe(int x, int y);
void removeBlock();
void moveBlock();

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for(int i=mapY-1; i>=0; i--){
        for(int j=0; j<mapX; j++){
            cin >> board[j][i];
        }
    }
    
    int chain = -1;
    bool isChain;
    do{
        isChain = false;
        chain++;
        memset(visit, 0, sizeof(visit));
        
        for(int i=0; i<mapX; i++){
            for(int j=0; j<mapY; j++){
                if(board[i][j]!='.' && !visit[i][j]){
                    checkedBlock = vector<Point>();
                    checkBlock(i, j, board[i][j]);
                    
                    if(checkedBlock.size() >= 4){
                        isChain = true;
                        removeBlock();
                    }
                }
            }
        }
        moveBlock();
    }while(isChain);
    
    cout << chain << endl;
    
    return 0;
}

void checkBlock(int x, int y, char block){
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(!isSafe(nx,ny) || visit[nx][ny] || board[nx][ny]!=block)  continue;
        
        visit[nx][ny] = VISITED;
        checkedBlock.push_back(Point(nx, ny));
        checkBlock(nx, ny, block);
    }
}

bool isSafe(int x, int y){
    return (x>=0 && x<mapX && y>=0 && y<mapY);
}

void removeBlock(){
    for(Point block : checkedBlock){
        board[block.x][block.y] = '.';
    }
}

void moveBlock(){
    for(int i=0; i<mapX; i++){
        char tmp[13] = {'.','.','.','.','.','.','.','.','.','.','.','.','.'};
        int tmpIndex = 0;
        for(int j=0; j<mapY; j++){
            if(board[i][j] != '.'){
                tmp[tmpIndex++] = board[i][j];
            }
        }
        memcpy(board[i], tmp, sizeof(char) * 13);
    }
}
    OracleデータベースのSQL単行関数---文字関数続き
    カフカ、Go、PostgresとGraphicsを使用してページビューの解析システムを作成する