Lv 3柱とビームの取り付け

5057 ワード

質問する


氷河が砕けるにつれて、雪城に漂ってきた「ジョルディ」は人生の第2幕のため、住宅建築事業に身を投じることを決意した.「ジョルディ」は柱と梁を利用して壁面構造を自動的に構築するロボットを開発する計画で、これまでロボットの動作をシミュレートするプログラムを作成していた.
このプログラムでは、2 D仮想壁面に柱と梁を使用して、柱とビューの長さが1のセグメントとして表されるフレーム構造をインストールできます.次のルールがあります.
  • 柱は、底部、梁の一端、または他の柱に配置する必要があります.
  • 梁の一端は柱に位置するか、両端は他の梁と同時に接続しなければならない.
  • しかし、床とは壁の底の床のこと.
    2 D壁面がn x nサイズの正射メッシュで、各メッシュサイズが1 x 1です.最初の壁面は空です.柱と梁は、グリッド線の交点ではなく、グリッドの各エッジに取り付けることができます.次に、柱と梁を取り付けてフレームを作成する例を示します.

    たとえば、上図は次の手順で構造を作成します.
  • (1,0)から柱を上に取り付け、(1,1)から右にビームを作成します.
  • (2,1)から柱を上に取り付け、(2,2)から右にビームを作成します.
  • (5,0)から1本の柱を上に取り付け、(5,1)からもう1本の柱を上に取り付けます.
  • (4,2)からビームを右に取り付け、次に(3,2)からビームを右に取り付けます.
  • (4,2)右側のビームを最初に取り付けず,(3,2)右側のビームを取り付けてみると,2番ルールに合わないため取り付けられない.柱と梁を削除する機能もあり、柱と梁を削除した後、残りの柱と梁も上記のルールを満たすべきです.実行した操作が条件を満たしていない場合は、その操作は無視されます.
    2 D配列build frameにパラメータが付与されている場合、壁面サイズn、柱、梁をインストールまたは削除する操作を含み、すべてのコマンドを実行した後に構造の状態に戻ります.
    せいげんじょうけん

  • nは5以上100以下の自然数である.

  • build frameの垂直(行)長さは1000を超えない.

  • build frameの水平(列)長は4です.

  • build frameの要素は[x,y,a,b]である.
  • x、yは柱、梁の交点を取り付けたり削除したりする座標で、「水平座標、垂直座標」形式です.
  • aは、取り付けまたは削除する構造のタイプを示し、0は柱、1は梁を表す.
  • bはインストールまたは削除する構造を示し、0は削除を示し、1はインストールを示す.
  • 壁面の外に柱、梁を取り付けない.
    床にビームを取り付ける場合はありません.

  • 交差座標から構造の右側を表示し、柱を上から取り付けたり削除したりします.

  • インストールされた構造が重複している場合、または存在しない構造が削除されている場合は、入力は提供されません.

  • 最終構築物の状態は以下の規則に従って戻ってください.
  • を返す配列には、各構造の座標が含まれ、3つの水平(列)の長さを持つ2次元配列が必要です.
  • の配列を返す要素は[x,y,a]形式です.
  • x,yは柱・梁の交点座標,[横座標,縦座標]形式である.
  • 柱は、ビューの交差点座標の右側または上に取り付けられていることを示します.
  • aは構造のタイプを表し、0は柱を表し、1は梁を表す.
  • を返す配列はx座標昇順で並べられ、x座標が同じ場合はy座標昇順で並べられます.
  • xとy座標が同じであれば、柱は梁の前にあります.
  • I/O例
    nbuild_frameresult5[[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]][[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]]5[[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]][[0,0,0],[0,1,1],[1,1,1],[2,1,1],[3,1,1],[4,0,0]]
    I/O例説明
    I/O例#1
    問題の例.
    I/O例#2
    8番目のタスクを実行すると、次の構造が作成されます.

    9番目の操作では、(1,1)から右側のビームを削除すると、右側の表示条件が満たされないため(2,1)は無視されます.
    10番目の操作では、(2,2)内の上向きの柱は条件を満たさないため、無視されます.

    に答える


    条件を満たす実施問題

    コード#コード#

    def solution(n, build_frame):
        mat = [[[0]*2 for _ in range(n+1)] for _ in range(n+1)]
        answer = []
        for b in build_frame:
            r = b[0]
            c = b[1]
            if b[3]:
                if b[2]:
                    if check_beam(n,b[0],b[1],mat):
                        answer.append([b[0],b[1],1])
                        mat[b[0]][b[1]][1] = 1
                else:
                    if check_column(n,b[0],b[1],mat):
                        answer.append([b[0],b[1],0])
                        mat[b[0]][b[1]][0] = 1
            else:
                if b[2]:
                    mat[r][c][1] = 0
                    if r < n and mat[r+1][c][0] == 1:
                        if not check_column(n,r+1,c,mat):
                            mat[r][c][1] = 1
                            continue
                    if r < n and mat[r+1][c][1] == 1:
                        if not check_beam(n,r+1,c,mat):
                            mat[r][c][1] = 1
                            continue
                    if mat[r][c][0] == 1:
                        if not check_column(n,r,c,mat):
                            mat[r][c][1] = 1
                            continue
                    if r > 0 and mat[r-1][c][1] == 1:
                        if not check_beam(n,r-1,c,mat):
                            mat[r][c][1] = 1
                            continue
                    answer.remove([r,c,1])
                else:
                    mat[r][c][0] = 0
                    if c < n and mat[r][c+1][0] == 1:
                        if not check_column(n,r,c+1,mat):
                            mat[r][c][0] = 1
                            continue
                    if c < n and mat[r][c+1][1] == 1:
                        if not check_beam(n,r,c+1,mat):
                            mat[r][c][0] = 1
                            continue
                    if r > 0 and c < n and mat[r-1][c+1][1] == 1:
                        if not check_beam(n,r-1,c+1,mat):
                            mat[r][c][0] = 1
                            continue
                    answer.remove([r,c,0])
        return sorted(answer, key=lambda x: (x[0],x[1],x[2]))
    
    def check_column(n,r,c,mat):
        if c == 0:
            return True
        if r > 0 and mat[r-1][c][1] == 1: 
            return True
        if mat[r][c][1] == 1:
            return True
        if c > 0 and mat[r][c-1][0] == 1:
            return True
    
    def check_beam(n,r,c,mat):
        if c > 0 and mat[r][c-1][0] == 1:
            return True
        if r < n and c > 0 and mat[r+1][c-1][0] == 1:
            return True
        if r > 0 and mat[r-1][c][1] == 1 and r < n and mat[r+1][c][1] == 1:
            return True