操作はしご(15684)

1.質問

質問リンク

2.解答

2-1. 条件

横線を連続的に設定できません.

横線は4本以上設置できません.

2-2. に答える

はしごを取り付けるすべての状況の数にナビゲートします.
すべての垂直線が一致していることを確認します.
計画を立て,逐次漸進的に実施する.
計画1-勾配水平線の設置情報を2 D booleanアレイに格納します.
まずは私が一番大切だと思う部分から始めましょう
現実の勾配ゲームのコンピュータをどのようにデータ化しますか?
前から強調してきたが、半分は解決したと思っても過言ではない.
現実の複雑な問題をコンピュータが理解できるデータに変換する.
どのようなデータ構造を使用するかは、問題を困難にしやすくします.
2 D booleanアレイを宣言し、インストールされた水平線を保存します.

boolean[][] ladders = new boolean[H][N];

for (int i = 0; i < M; i++) {
   	stk = new StringTokenizer(br.readLine());
   	int a = Integer.parseInt(stk.nextToken()) - 1;
   	int b = Integer.parseInt(stk.nextToken()) - 1;
			
   	ladders[a][b] = true;
}

計画2-はしごを取り付けるすべての場合にナビゲートする数.
バックグラウンドトラッキングを使用して実装します.
インストールされ、
はしごが取り付ける部分の左側または右側に取り付けられている場合は、除外します.(1号条件)
そして前から貴い二本目の横線で探索を始めれば.
次の再帰では、水平線を2番目の水平線からパラメータに移動します.

for (int i = horizonLine; i < H; i++) {
	for (int j = 0; j < N - 1; j++) {
		// 사다리가 이미 설치돼있을 때
		if (ladders[i][j]) continue;
				
		// 왼쪽에 사다리가 있거나, 오른쪽에 사다리가 있는 경우 (연속해서 설치 불가)
		if ((j - 1 >= 0 && ladders[i][j - 1]) || ladders[i][j + 1]) continue;
				
		ladders[i][j] = true;
		ret = Math.min(ret, min(fitCount + 1, i));
		ladders[i][j] = false;
	}
}

計画3-垂直線が互いにマッピングされていることを確認します.
最初の繰り返し文は、垂直線ごとにナビゲートするために使用されます.
2番目の繰り返し文は、垂直線に取り付けられた水平線に沿って移動します.
移動した位置が垂直線にマップされていない場合は、ループを終了します.
N-1の縦線にマッピングすると
N番目の垂直線は当然マッピングされるのでチェックしません.

// 사다리 검사
boolean flag = true;
		
for (int i = 0; i < N - 1; i++) {
	int pos = i;
			
	for (int j = 0; j < H; j++) {
		if (ladders[j][pos]) {
			pos++;
		}
		else if (pos - 1 >= 0 && ladders[j][pos - 1]) {
			pos--;
		}
	}
			
	if (pos != i) {
		flag = false;
		break;
	}
}

3.完全なコード

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N, M, H;
	static final int INF = 4;
	static boolean[][] ladders;
	
	static int min(int fitCount, int horizonLine) {
		// 기저 사례 3번 안에 성공시켜야 함
		if (fitCount > 3) return INF;
		
		// 계획 3 - 세로선이 서로 매핑하는지 확인합니다.
		// 사다리 검사
		boolean flag = true;
		
		for (int i = 0; i < N - 1; i++) {
			int pos = i;
			
			for (int j = 0; j < H; j++) {
				if (ladders[j][pos]) {
					pos++;
				}
				else if (pos - 1 >= 0 && ladders[j][pos - 1]) {
					pos--;
				}
			}
			
			if (pos != i) {
				flag = false;
				break;
			}
		}
		
		// 매핑된다면 설치 개수 리턴
		if (flag) return fitCount;
		
		int ret = INF;
		
		// 계획 2 - 사다리를 설치하는 모든 경우의 수를 탐색합니다.
		for (int i = horizonLine; i < H; i++) {
			for (int j = 0; j < N - 1; j++) {
				// 사다리가 이미 설치돼있을 때
				if (ladders[i][j]) continue;
				
				// 왼쪽에 사다리가 있거나, 오른쪽에 사다리가 있는 경우 (연속해서 설치 불가)
				if ((j - 1 >= 0 && ladders[i][j - 1]) || ladders[i][j + 1]) continue;
				
				ladders[i][j] = true;
				ret = Math.min(ret, min(fitCount + 1, i));
				ladders[i][j] = false;
			}
		}
		
		return ret;
	}
	
	public static void main(String[] args) throws Exception {
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(stk.nextToken());
		M = Integer.parseInt(stk.nextToken());
		H = Integer.parseInt(stk.nextToken());
		
		ladders = new boolean[H][N];
		
		// 계획 1 - 사다리 가로선의 설치 정보를 2차원 boolean배열에 저장합니다.
		for (int i = 0; i < M; i++) {
			stk = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(stk.nextToken()) - 1;
			int b = Integer.parseInt(stk.nextToken()) - 1;
			
			ladders[a][b] = true;
		}
		
		int ans = min(0, 0);
		
		bw.write((ans == INF ? -1 : ans) + "");
		bw.close();
	}
}

同様の問題は研究所である.