152.柱梁取付

34432 ワード
アルゴリズム#アルゴリズム# テキストリンク
プログラマ

  • 氷河が砕けるにつれて、雪城に漂ってきた「ジョルディ」は人生の第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次元配列nが与えられた場合、solution関数を完了し、すべてのコマンドを実行した後に構造の状態に戻り、壁面のサイズbuild_frame、柱、梁を取り付けまたは削除します.

    • 1. Python

    
def possible(answer):
    for x, y, stuff in answer:
        if stuff == 0: #기둥
            #바닥 위, 보의 한쪽 끝부분 위, 다른 기둥 위
            if y == 0 or [x - 1, y, 1] in answer or [x, y, 1] in answer or [x, y - 1, 0] in answer:
                continue
            return False
        if stuff == 1: #보
            #한쪽 끝부분이 기둥 위, 양쪽 끝부분이 다른 보와 동시에 연결
            if [x, y - 1, 0] in answer or [x + 1, y - 1, 0] in answer or ([x - 1, y, 1]) in answer and [x + 1, y, 1] in answer:
                continue
            return False
    return True
                
def solution(n, build_frame):
    answer = []
    for frame in build_frame: 
        x, y, stuff, operate = frame
        if operate == 0: #삭제하는 경우
            answer.remove([x, y, stuff])  #일단 삭제
            if not possible(answer): #가능한 구조인지 확인
                answer.append([x, y, stuff]) #가능하지 않으면 다시 설치
        if operate == 1:
            answer.append([x, y, stuff]) #일단 설치
            if not possible(answer):
                answer.remove([x, y, stuff])
    
    return sorted(answer) #정렬된 결과 반환

  • コマンド総数がMの場合、O(M)²)非常に理想的であるが,時間制限は5秒,O(M)である.³) のアルゴリズムも可能です.
  • は、インストールおよび削除操作が要求されるたびに、構造全体を個別にチェックし、ルールを確認することができる.
  • possible関数を呼び出して、現在の構造が正常であるかどうかを確認します.正常でない場合、現在の演算は無視されます.

    • 2. C++

    
#include <bits/stdc++.h>

using namespace std;

// 현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
bool possible(vector<vector<int> > answer) {
    for (int i = 0; i < answer.size(); i++) {
        int x = answer[i][0];
        int y = answer[i][1];
        int stuff = answer[i][2];
        if (stuff == 0) { // 설치된 것이 '기둥'인 경우
            bool check = false;
            // '바닥 위'라면 정상
            if (y == 0) check = true;
            // '보의 한 쪽 끝 부분 위' 혹은 '다른 기둥 위'라면 정상
            for (int j = 0; j < answer.size(); j++) {
                if (x - 1 == answer[j][0] && y == answer[j][1] && 1 == answer[j][2]) {
                    check = true;
                }
                if (x == answer[j][0] && y == answer[j][1] && 1 == answer[j][2]) {
                    check = true;
                }
                if (x == answer[j][0] && y - 1 == answer[j][1] && 0 == answer[j][2]) {
                    check = true;
                }
            }
            if (!check) return false; // 아니라면 거짓(False) 반환
        }
        else if (stuff == 1) { // 설치된 것이 '보'인 경우
            bool check = false;
            bool left = false;
            bool right = false;
            // '한쪽 끝부분이 기둥 위' 혹은 '양쪽 끝부분이 다른 보와 동시에 연결'이라면 정상
            for (int j = 0; j < answer.size(); j++) {
                if (x == answer[j][0] && y - 1 == answer[j][1] && 0 == answer[j][2]) {
                    check = true;
                }
                if (x + 1 == answer[j][0] && y - 1 == answer[j][1] && 0 == answer[j][2]) {
                    check = true;
                }
                if (x - 1 == answer[j][0] && y == answer[j][1] && 1 == answer[j][2]) {
                    left = true;
                }
                if (x + 1 == answer[j][0] && y == answer[j][1] && 1 == answer[j][2]) {
                    right = true;
                }
            }
            if (left && right) check = true;
            if (!check) return false; // 아니라면 거짓(False) 반환
        }
    }
    return true;
}

vector<vector<int> > solution(int n, vector<vector<int> > build_frame) {
    vector<vector<int> > answer;
    // 작업(frame)의 개수는 최대 1,000개
    for (int i = 0; i < build_frame.size(); i++) {
        int x = build_frame[i][0];
        int y = build_frame[i][1];
        int stuff = build_frame[i][2];
        int operate = build_frame[i][3];
        if (operate == 0) { // 삭제하는 경우
            // 일단 삭제를 해 본 뒤에
            int index = 0;
            for (int j = 0; j < answer.size(); j++) {
                if (x == answer[j][0] && y == answer[j][1] && stuff == answer[j][2]) {
                    index = j;
                }
            }
            vector<int> erased = answer[index];
            answer.erase(answer.begin() + index);
            if (!possible(answer)) { // 가능한 구조물인지 확인
                answer.push_back(erased); // 가능한 구조물이 아니라면 다시 설치
            }
        }
        if (operate == 1) { // 설치하는 경우
            // 일단 설치를 해 본 뒤에
            vector<int> inserted;
            inserted.push_back(x);
            inserted.push_back(y);
            inserted.push_back(stuff);
            answer.push_back(inserted);
            if (!possible(answer)) { // 가능한 구조물인지 확인
                answer.pop_back(); // 가능한 구조물이 아니라면 다시 제거
            }
        }
    }
    // 정렬된 결과를 반환
    sort(answer.begin(), answer.end());
    return answer;
}
    白俊2845番パーティーが終わったら答えます
    Centosファイアウォールコマンドが見つかりません