[未解決の問題]HELP ME...プログラマーsweekleyは3週間のパズルブロックに挑戦します

昨日解答しようとした問題はプログラマーsweekleyが3週間のパズルに挑戦題です.
実は、3週目の問題が来て、私はよく問題を読みました.破片はBFSで見つけた...そして、どうしようか考えています.似たような問題があったので、Kakao機から出た鍵と鍵(位置を見に行く)を外しました.二次元配列を利用した朴九九のようだ.

ヘルプのリクエスト🔥

とにかく、私は先に似たような問題を解決して、昨日私はこの問題を解決しようとしましたが、ずっと6つのテックが合格しなかったので、私は彼を捕まえて、最後に諦めました.😭 次の質問と解答方法とコードをアップロードします!そして私も真剣にコメントを書きました!どこに問題があるのか気づいたら、ぜひコメントを書いてくださいね

問題の説明

テーブルの上のパズルの破片をゲームボードの空白に適当に置きたいです.ゲームボードとデスクトップは正方形のメッシュで、各セルのサイズは1 x 1です.次の規則に従って、テーブルの上のパズルブロックをゲームボードのスペースに埋めます.

を一度に充填します.

セグメントを回転できます.

ブロックを反転できません.

ゲームボードには、新しく埋め込まれたパズルブロックに隣接するスペースはありません.

次に、パズルセグメントを塗りつぶす例を示します.

上図では、左側に現在のゲームボードの状態が表示され、右側にデスクトップのパズルの破片が表示されます.デスクトップ上のパズルブロックにも「上」、「下」、「左」、「右」が隣接していない場合、スペースはパズルの空白がないことを示します.すべてのパズルセグメントはグリッドにちょうど配置されており、エラーは配置されていません(たとえば、グリッドから離れたり、グリッドを越えたりします).
3番目、4番目、5番目のセグメントをグリッドに配置すると、以下のようにルールに違反しているため、不可能です.

3番の破片を配置します.4番の破片を配置する前に、上に隣接するセルにスペースが表示されます.

5号彫刻の両側に隣接する格子にスペースを生成します.

次はゲームボードにできるだけ多くの破片をルールに従って埋めます.

破片をできるだけ多く充填し、合計14格子を充填することができます.
パラメータは,現在のゲームボードの状態game board,表上のパズルブロックの状態表である.可能な限り多くのスペルブロックをルールに従って埋め込む場合は、solution関数を完了して、合計でどれだけのグリッドを埋め込むことができるかを返します.

せいげんじょうけん

3≦game board総裁≦50

game boardの各列の長さ=game boardの行の長さ

、すなわち、ゲームボードは正方形メッシュである.

game boardのすべての要素は0または1です.

0はスペースを表し、1は埋め込まれたスペースを表します.

個のパズルセグメントのスペースを配置するには、少なくとも1つの1 x 1サイズの正方形、最大6個が必要です.

表の行長=game boardの行長

表の各列の長さ=表の行の長さ

すなわち、テーブルはgame boardと同じ大きさの正方形メッシュである.

表のすべての要素は0または1です.

0はスペース、1は破片のあるスペースを表します.

パズルブロックの大きさは1つの1 x 1の正方形で、少なくとも1つから最大6つまでです.

game boardには1つ以上のスペースが必要です.

テーブルには、1つ以上のブロックが含まれている必要があります.

I/O例

game_boardtableresult[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]][[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]]14[[0,0,0],[1,1,0],[1,1,1]][[1,1,1],[1,0,0],[0,0,0]]0

解答方法

積み木を出せ!

まず,テーブルのレイアウトを探索し,各ブロックを分離する.まず,ブロックがどのような形で格納され表現されるべきかを考えた.次に、まずブロックを抽出するために、テーブルでbfsを検索し、接続された1で検索し、テーブルと同じサイズの配列で対応する座標のみを1に変更し、ブロックの形状をスケールで表します.
また、このようにすると、残りのスペースが多くなり、後で看板や閲覧を行う際に効率が低下するので、行や列を閲覧するとともに、1の行や列がないと判断してブロックが置かれているコンパクトな空間を知ることができる.
このように、ブロック形状の配列や、ブロックが存在する空間の開始座標と終了座標、およびその後結果値を導出するために必要なブロックのセル数などを格納する必要があるため、blockクラスが作成され、関連する属性と関数が分離される.

抜いたブロックがプレートに入っているかどうかを確認します!

まず、ブロックは回転可能であるため、各方向について以下の確認手順を行う必要がある.したがって、回転関数が確立され、使用されます.この場合、アレイを回転させるだけでなく、幅の高さやアレイ内のブロックが置かれている空間ビームの始点や終点座標なども変更するので、一緒に更新します!
プレートの左上から右下に1マスずつ移動し、ブロックがその位置に入るか否かを判断します.このときの判断基準は以下の3つである.

板もブロックもゼロにできません!

板もブロックも1ではありません!

元の真外にゼロをつなぐことはできません!(続いて、全てが充填する空白空間、すなわち隣接する空白空間)

.
ここで1と2は碁盤と碁盤が同じ位置にあると判断すれば良いのですが、3番は碁盤の四面端に0があれば、外の要素が0であることを確認すれば良いのです!
以上のすべての条件を通過してちょうど良いと判断すれば、そのブロックが入ることができるので、碁盤の位置を1で埋め尽くし、ブロックの格数に応じて答えを増やしました!

コード#コード#

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public static int[] dx = {0, 1, 0, -1};
    public static int[] dy = {1, 0, -1, 0};

    public static class Point{
        private int x;
        private int y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }

        public void plusX() {
            this.x++;
        }

        public void plusY() {
            this.y++;
        }

        public void minusX(){
            this.x--;
        }

        public void minusY(){
            this.y--;
        }
    }

    public static class Block{
        private int[][] block; // 블록 배열, table, board와 사이즈 동일
        private int count; // 블록의 개수
        private int size; // 배열의 가로세로 사이즈, 즉 table board 사이즈랑 동일
        private Point startIndex, endIndex; // 테이블 전체에서 하나만 뽑았기에 빈 공간이 많아서 블록만을 다루기 위해서 블록의 시작점(좌측상단) 끝점(우측하단)을 가지고있음
        private int width, height; // 바로 위의 시작 끝과 어찌보면 중복되는 정보 ? block 배열 자체가 아닌 1이 차있는 찐 블록이 있는 공간의 너비 높이


        Block(int n){
            this.size = n;
            this.block = new int[size][size];
            this.count = 0;
            this.startIndex = new Point(0,0);
            this.endIndex = new Point(size-1, size-1);
            this.width = n;
            this.height = n;
        }

        // 해당 조각의 시작점부터 이어진 점을 bfs로 탐색하여 하나의 조각 완성
        public void init(int[][] table, boolean[][] visited, Point start){
            Queue<Point> queue = new LinkedList<>();
            Point current, next;
            queue.add(start);
            visited[start.x][start.y] = true;
            while (!queue.isEmpty()){
                current = queue.poll();
                block[current.x][current.y] = 1;
                count++;
                for(int k=0; k<4; k++){
                    next = new Point(current.x+dx[k], current.y+dy[k]);
                    if(next.x >= 0 && next.x < size && next.y >= 0 && next.y < size && !visited[next.x][next.y] && table[next.x][next.y] == 1){
                        queue.add(next);
                        visited[next.x][next.y] = true;
                    }
                }
            }
            // 배열 사이즈가 table 사이즈와 동일하기 때문에 진짜 블록이 위치하는 위치를 뽑아내기 위한 함수 호출
            removeEmptyLine();
        }

        // 첫 행, 끝 행, 첫 열, 끝 열을 각각 확인하면서 만일 1이 존재하지 않으면 블록이 존재하는 찐 위치를 위한 변수를 조정해준다.
        public void removeEmptyLine(){
            boolean xStart, xEnd, yStart, yEnd;
            xStart = true;
            xEnd = true;
            yStart = true;
            yEnd = true;
            for(int i=0; i<size; i++){
                for(int j=0; j<size; j++){
                    if(block[i][j] != 0) xStart = false;
                    if(block[size-1-i][j] != 0) xEnd = false;
                    if(block[j][i] != 0) yStart = false;
                    if(block[j][size-1-i] != 0) yEnd = false;
                }
                if(xStart){
                    startIndex.plusX();
                    height--;
                }
                if(xEnd){
                    endIndex.minusX();
                    height--;
                }
                if(yStart){
                    startIndex.plusY();
                    width--;
                }
                if(yEnd){
                    endIndex.minusY();
                    width--;
                }
                if(!xStart && !xEnd && !yStart && yEnd) break;
            }
        }

        // 말그대로 블록 회전 !
        public void rotation(){
            int[][] result = new int[block[0].length][block.length];
            int temp;
            for(int i=0; i<block.length; i++){
                for(int j=0; j<block[0].length; j++){
                    result[j][size-1-i] = block[i][j];
                }
            }
            block = result;

            // 너비 높이도 스왑 !
            temp = width;
            width = height;
            height = temp;

            // 시작점 ( 좌측상단 ) 끝점 ( 우측하단 ) 도 바뀌므로 업데이트 !
            Point newStart = new Point(startIndex.y, size-1-endIndex.x);
            Point newEnd = new Point(endIndex.y, size-1- startIndex.x);
            this.startIndex = newStart;
            this.endIndex = newEnd;
        }
    }

    // 블록이 들어갈 수 있는지 판단하는 함수
    public static boolean isPossible(Block block, int[][] board){
        boolean result;
        // 네 방향에 대해서
        for(int i=0; i<4; i++){
            // 첫 상태는 로테이션 하지 않음 ~
            if(i != 0) block.rotation();
            // 블록을 옮기면서
            for(int a=0; a<=board.length- block.height; a++){
                for(int b=0; b<=board.length-block.width; b++){
                    result = true;
                    // 블록이 해당 위치에 들어갈 수 있는지 판단
                    for(int c=0; c<block.height; c++){
                        for(int d=0; d<block.width; d++){
                            // 블록과 게임보드의 원소가 같으면 안된다. ( 둘 다 1이면 들어갈 수 없고, 둘 다 0이면 채워지지 않음 )
                            if(board[a+c][b+d] == block.block[c+block.startIndex.x][d+block.startIndex.y]) {
                                result = false;
                                break;
                            }
                            // 위의 조건을 다 만족해서 들어갈 수 있을 때, 블록의 범위외에 인접한 빈 공간이 있는지 확인 !
                            // 블록의 경계를 기준으로 x축 최상단 최하단 y축 최좌측 최우측에 대해서 해당 공간이 비어있어서 board의 원소가 0이고, 인접한 0 위치가 0인지 확인 !
                            if(c==0 && a!=0) if(board[a+c][b+d] == 0 && board[a+c-1][b+d] == 0){
                                result = false;
                                break;
                            }
                            if(c==block.height-1 && a!=board.length- block.height) if (board[a+c][b+d] == 0 && board[a+c+1][b+d] == 0){
                                result = false;
                                break;
                            }
                            if(d==0 && b!=0) if (board[a+c][b+d] == 0 && board[a+c][b+d-1] == 0){
                                result = false;
                                break;
                            }
                            if(d==block.width-1 && b!= board.length- block.width) if (board[a+c][b+d] == 0 && board[a+c][b+d+1] == 0){
                                result = false;
                                break;
                            }
                        }
                        if(!result) break;
                    }
                    // 위의 조건을 모두 통과해서 블록이 들어갈 수 있으면, 넣어주고( 즉 들어갈 위치를 1로 업데이트 해주고 ) 들어갈 수 있음을 의미하는 true 반환
                    if(result){
                        for(int c=0; c<block.height; c++) {
                            for (int d = 0; d < block.width; d++) {
                                board[a+c][b+d] += block.block[c+block.startIndex.x][d+block.startIndex.y];
                            }
                        }
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    public int solution(int[][] game_board, int[][] table) {
        int answer = 0;
        ArrayList<Block> blocks = new ArrayList<>();
        Block block;
        boolean[][] visited = new boolean[table.length][table.length]; // bfs를 위한 visited
        // 각 원소들을 탐색하면서 방문하지 않은 1을 만나면 bfs로 블록 한 조각을 만들어서 리스트에 넣어준다.
        for(int i=0; i<table.length; i++){
            for(int j=0; j<table.length; j++){
                if(table[i][j] == 1 && !visited[i][j]){
                    block = new Block(table.length);
                    block.init(table, visited, new Point(i, j));
                    blocks.add(block);
                }
            }
        }

        // 각 블록들에 대해서 들어갈 수 있는지 탐색해서 들어갈 수 있으면 해당 블록이 구성된 조각의 수만큼 answer 증가
        for (Block value : blocks) if (isPossible(value, game_board)) answer += value.count;
        return answer;
    }
}