[プログラマー]友達4ブロック

18540 ワード
2018 KAKAO BLIND RECRUITMENT プログラマ supin2 cpp level2 テキストリンク
回答日:2021-07-26

質問する


質問リンク:https://programmers.co.kr/learn/courses/30/lessons/17679

アクセスと解析


与えられた配列の大きさは最大30 x 30で、あまり大きくないので、完全に探ってみればいいと思います.
実装には以下のアルゴリズムが採用されている.
  • (0,0)点から(m−2,n−2)まで.
  • でナビゲートする場合、各位置において、右、下、右下(対角線方向)に同じ形状のブロックがあればマーキングする.
  • と表示されているブロックを「0」に変換します.
  • の角列を押してブロックを下に落とします.
  • と表示されているブロックがないまで.最初から繰り返す.
    • (m−2,n−2)を探索したのは,正方形を検査する際に範囲を超えないためである.これは実現しにくい問題のようだ.
    より容易に実現できるかもしれませんが、与えられた問題の順序で実現されただけです.

    コード#コード#

    #include <string>
#include <vector>
#include <cstring>

using namespace std;

int M, N;
vector<string> cBoard;

bool visited[31][31];
int dir[3][2] = {{ 1, 0 }, { 1, 1 }, { 0, 1 }};

bool square_check(int y, int x, char ch) {
    bool flag = true;
    for (int n = 0; n < 3; n++) {
        if (cBoard[y + dir[n][0]][x + dir[n][1]] != ch) {
            flag = false;
            break;
        }
    }
    if (flag) {
        visited[y][x] = true;
        for (int n = 0; n < 3; n++) {
            visited[y + dir[n][0]][x + dir[n][1]] = true;
        }
    }
    return flag;
}

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    M = m, N = n, cBoard = board;
    bool erase = false;

    do {
        erase = false;
        memset(visited, false, sizeof(visited));
        for (int i = 0; i < m - 1; i++) { // 지울 블록 체크
            for (int j = 0; j < n - 1; j++) {
                if (cBoard[i][j] != '0') {
                    if (square_check(i, j, cBoard[i][j])) {
                        erase = true;
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) { // 블록 지우기('0'으로 치환)
            for (int j = 0; j < n; j++) {
                if (visited[i][j] == true) {
                    cBoard[i][j] = '0';
                    answer++;
                }
            }
        }
        int y, x;
        for (int i = 0; i < n; i++) { // 각 열별로 블록들 떨어트리기
            for (int j = m - 1; j >= 0; j--) {
                if (cBoard[j][i] == '0') {
                    y = j, x = i;
                    bool change = false;
                    while (true) {
                        y--;
                        if (y < 0) {
                            break;
                        }
                        if (cBoard[y][x] != '0') {
                            change = true;
                            break;
                        }
                    }
                    if (change == true) {
                        cBoard[j][i] = cBoard[y][x];
                        cBoard[y][x] = '0';
                    }
                }
            }
        }
    } while (erase); // 지워지는게 없으면 종료
    return answer;
}

    結果



    フィードバック


    実施能力は重要な問題のようだ.
    Dockerコンテナデータボリューム(Data Volume)とデータ管理
    HTML level.2