実施-6.ビーム取り付け

質問する

氷河が砕けるにつれて、雪城に漂ってきた「ジョルディ」は人生の第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例説明
I/O例#1
問題の例.
I/O例#2
8番目のタスクを実行すると、次の構造が作成されます.

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

インプリメンテーションコード

import java.util.*;

class Node implements Comparable<Node>{
	private int x;
	private int y;
	private int a;
	public Node(int x, int y, int a) {
		this.x = x;
		this.y = y;
		this.a = a;
	}
	
	public int getX(){
		return x;
	}
	public int getY(){
		return y;
	}
	public int getA(){
		return a;
	}
	
	@Override
	public int compareTo(Node other) {
		if(this.x == other.x && this.y == other.y ) {
			return Integer.compare(this.a, other.a);
		}
		else if(this.x == other.x) {
			return Integer.compare(this.y, other.y);
		}
		return Integer.compare(this.x, other.x);
	}
}


class Solution {

	public boolean check(ArrayList<ArrayList<Integer>>answer){
		for(int i = 0; i < answer.size(); i++){
			int x = answer.get(i).get(0);
			int y = answer.get(i).get(1);
			int a = answer.get(i).get(2);
			//	기둥
			if(a == 0){
				boolean ck = false;
				// 바닥
				if(y == 0) ck = true;
				else{
					for(int j = 0; j < answer.size(); j++){
						// 기둥위
						if(x == answer.get(j).get(0) && y-1 == answer.get(j).get(1) && answer.get(j).get(2) == 0){
							ck = true;
						}
						// 보 오른쪽
						else if(x-1 == answer.get(j).get(0) && y == answer.get(j).get(1) && answer.get(j).get(2) == 1){
							ck = true;
						}
						// 보 왼쪽
						else if(x == answer.get(j).get(0) && y == answer.get(j).get(1) && answer.get(j).get(2) == 1){
							ck = true;
						}
					}
					if(!ck) return false;
				}

			}
			// 보
			else if(a == 1){
				boolean ck = false;
				boolean left = false;
				boolean rigth = false;
				for(int j = 0; j <answer.size() ; j++){
					//기둥위 왼쪽
					if(x == answer.get(j).get(0) && y-1 == answer.get(j).get(1) && answer.get(j).get(2) == 0){
						ck = true;
					}
					//기둥위 오른쪽
					else if(x+1 == answer.get(j).get(0) && y-1 == answer.get(j).get(1) && answer.get(j).get(2) == 0){
						ck = true;
					}
					//보 왼쪽
					if(x-1 == answer.get(j).get(0) && y == answer.get(j).get(1) && answer.get(j).get(2) == 1){
						left = true;
					}
					//보 오른쪽
					if(x+1 == answer.get(j).get(0) && y == answer.get(j).get(1) && answer.get(j).get(2) == 1){
						rigth = true;
					}
				}
				if(rigth && left) ck =true;
				if(!ck) return false;
			}
		}
		
		return true;
	}

    public int[][] solution(int n, int[][] build_frame) {
		ArrayList<ArrayList<Integer>>answer = new ArrayList<>();
		for(int i = 0;i <build_frame.length; i++){
			int x = build_frame[i][0];
			int y = build_frame[i][1];
			int a = build_frame[i][2];
			int b = build_frame[i][3];
			if(b == 0){
				for(int j = 0; j < answer.size();j++){
					if(x == answer.get(j).get(0) && y == answer.get(j).get(1) && a == answer.get(j).get(2)){
						ArrayList<Integer>del = answer.get(j);
						answer.remove(j);
						if(!check(answer)){
							answer.add(del);
						}
					}
				}
			}
			if(b == 1){
				ArrayList<Integer>insert = new ArrayList<>();
				insert.add(x);
				insert.add(y);
				insert.add(a);
				answer.add(insert);
				if(!check(answer)){
					answer.remove(answer.size()-1);
				}
			}
		}
		
		ArrayList<Node>list = new ArrayList<>();
		for(int i = 0; i < answer.size(); i++){
			list.add(new Node(answer.get(i).get(0), answer.get(i).get(1), answer.get(i).get(2)));
		}
		Collections.sort(list);
		
        int[][] result = new int[list.size()][3];
		for(int i = 0; i < list.size(); i ++){
			result[i][0] = list.get(i).getX();
			result[i][1] = list.get(i).getY();
			result[i][2] = list.get(i).getA();
		}
        return result;
    }
}

コード解釈

これは典型的な実施問題であり,シミュレーション問題である.この問題を解くときは順番にやるのは難しい.1つ目のポイントは配列値をArrayListで比較することです建設するか削除するかによって区別する.値bが0(削除)の場合、bが1(建設)の場合、分割することができる.
また、削除・建設のため、削除・建設後に条件を満たしているかを確認する.したがって、操作を続行し、条件が満たされていることを確認し、条件が満たされていない場合は元の状態に戻すことができます.
条件をチェックすると、ArrayListの値が完全にナビゲートされて確認され、柱の場合と表示された場合、それぞれ確認されます.
最後に、条件が配列を返す場合はx座標昇順、x座標が同じ場合はy座標昇順で並べ替える必要があります.したがって、Compabiledインタフェースを継承すると、比較方法が上書きされます.