[白俊]15684号梯子操作(C++,三星機出)

22648 ワード
ついせき boj フルナビゲーション SWEA テキストリンク
https://www.acmicpc.net/problem/15684
タイムアウトが多くて大変でした.
はしごゲームの碁盤をmap変数に入れ、はしごがあるときは左に1、右に-1を置きます.
また、はしごを取り付ける場合は、重複しないように、無条件に左側にのみ取り付けます.
最初にエラーが発生した部分が返されると,2のfor文を用いて最初から探索しようとしたが,タイムアウトした.
Vectorを使用すると、この部分の検索が減少し、タイムアウトが解消されます.
    // vector를 이용한 탐색
	// 왼쪽과 오른쪽 모두 0일 때,
	// 사다리를 설치해준다.
	for(int i = idx; i < v.size(); i++) {
		point cur = v[i];
		if(map[cur.y][cur.x] == 0 && map[cur.y][cur.x + 1] == 0){
			map[cur.y][cur.x] = 1; map[cur.y][cur.x + 1] = -1;
			solve(i+1, depth + 1);
			map[cur.y][cur.x] = 0; map[cur.y][cur.x + 1] = 0;
		}
	}
この部分は主な論理です.
左側と右側に梯子がない場合は、再帰的に梯子を設定します.
また,深さは3より前に答えが出る可能性があるので,再帰に入る瞬間ごとにはしごを置いて計算する.
	// 사다리를 내려보는 함수
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		int y = 1;
		int x = i;
		// map이 1일 때, 사다리가 왼쪽으로 있으므로 x++
		// map이 -1일 때, 사다리가 오른쪽으로 있으므로 x--
		while (y <= h) {
			if (map[y][x] == 1) x++;
			else if (map[y][x] == -1) x--;
			// 한칸 내려준다.
			y++;
		}
		// 시작과 끝이 같으면 cnt++
		if (i == x)
			cnt++;
		else
			break;
	}
その部分は上の方法で計算したものです.
すべての縦線について、地図1は右、地図-1は左に移動します.

完全なコード

#include <iostream>
#include <vector>

using namespace std;

int n, m, h;
int map[31][11];
int answer = 987654321;
struct point {
public:
	int x;
	int y;
	point(int x, int y) {
		this->x = x;
		this->y = y;
	}
};
vector<point> v;

void solve(int idx, int depth) {
	// 3개 초과될 때 return
	if (depth == 4)
		return;
	
	// 사다리를 내려보는 함수
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		int y = 1;
		int x = i;
		// map이 1일 때, 사다리가 왼쪽으로 있으므로 x++
		// map이 -1일 때, 사다리가 오른쪽으로 있으므로 x--
		while (y <= h) {
			if (map[y][x] == 1) x++;
			else if (map[y][x] == -1) x--;
			// 한칸 내려준다.
			y++;
		}
		// 시작과 끝이 같으면 cnt++
		if (i == x)
			cnt++;
		else
			break;
	}

	// 사다리가 모두 자기자신으로 내려오면 
	// answer 갱신
	if (cnt == n) {
		answer = min(answer, depth);
	}

	// vector를 이용한 탐색
	// 왼쪽과 오른쪽 모두 0일 때,
	// 사다리를 설치해준다.
	for(int i = idx; i < v.size(); i++) {
		point cur = v[i];
		if(map[cur.y][cur.x] == 0 && map[cur.y][cur.x + 1] == 0){
			map[cur.y][cur.x] = 1; map[cur.y][cur.x + 1] = -1;
			solve(i+1, depth + 1);
			map[cur.y][cur.x] = 0; map[cur.y][cur.x + 1] = 0;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> h;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
		map[a][b + 1] = -1;
	}

	for (int i = 1; i <= h; i++)
		for (int j = 1; j < n; j++)
			if (map[i][j] == 0)
				v.push_back(point(j, i));

	solve(0,0);
	if (answer == 987654321)
		cout << "-1";
	else cout << answer;
}
[規格11053]最長成長部分数列(C++)
プログラマー:救命ボート