글 읽기 - 9%를 도저히 못넘네요.. 도움!!

suyeony 4년 전 0

BFS쓰고 조건 체크도 한 column이 false 나면 바로 다음에 놓을 사다리로 넘어가는 식인데 9%를 도저히 못넘네요..

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<climits>
#include<queue>
using namespace std;

vector<vector<int>> makeTable() {
	ifstream in("C:\\Users\\gjsgu\\Desktop\\Algorithm\\test_case\\test_case_for_ladder_rigging.txt");
	if (in.is_open()) cout << "file is opened." << endl;
	int N; int M; int H;
	in >> N; in >> M; in >> H;
	vector<vector<int>> table(H, vector<int>(2 * N - 1, 0));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < 2 * N - 1; j += 2) {
			table[i][j] = 1; // 1 is ladder
		}
	}
	int a; int b;
	for (int i = 0; i < M; i++) {
		in >> a; in >> b;
		table[a - 1][2 * (b - 1) + 1] = 2;// 2 is horizon line.
	}
	return table;
}

vector<vector<int>> makeTable2() {
	int N; int M; int H;
	cin >> N; cin >> M; cin >> H;
	vector<vector<int>> table(H, vector<int>(2 * N - 1, 0));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < 2 * N - 1; j += 2) {
			table[i][j] = 1; // 1 is ladder
		}
	}
	int a; int b;
	for (int i = 0; i < M; i++) {
		cin >> a; cin >> b;
		table[a - 1][2 * (b - 1) + 1] = 2;// 2 is horizon line.
	}
	return table;
}

vector<vector<int>> emptyHorizon(vector<vector<int>>& table) {
	vector<vector<int>> empty;
	for (int i = 0; i < table.size(); i++) {
		for (int j = 1; j < table[0].size(); j += 2) {
			if (table[i][j] == 0) empty.push_back({ i,j });
		}
	}
	return empty;
}

void printTable(vector<vector<int>>& table) {
	for (vector<int> row : table) {
		for (int i : row)
			cout << i << " ";
		cout << endl;
	}
}

inline int game(vector<vector<int>>& table, int pos) {
	for (int i = 0; i < table.size(); i++) {
		if (pos - 1 >= 0 && table[i][pos - 1] == 2) pos -= 2;
		else if (pos + 1 < table[0].size() && table[i][pos + 1] == 2) pos += 2;
	}
	return pos;
}

inline bool isSameEnd(vector<vector<int>> table) {
	for (int j = 0; j < table[0].size(); j += 2) {
		if (j != game(table, j)) return false;
	}
	return true;
}
inline vector<vector<int>> setLine(vector<vector<int>> table, int x, int y) {
	if ((y - 2 >= 0 && table[x][y - 2] == 2) || (y + 2 < table[0].size() && table[x][y + 2] == 2) || table[x][y] == 2)
		return {};
	table[x][y] = 2;
	return table;
}
int BFS(vector<vector<int>> table, vector<vector<int>> empty) {
	queue<pair<vector<vector<int>>, vector<int>>> que;
	que.push(make_pair(table, vector<int>{ 1, 0 }));
	int x; int y;
	vector<vector<int>> temp_table;
	int count = 1;
	int start;
	while (!que.empty()) {
		table = que.front().first;
		count = que.front().second[0];
		start = que.front().second[1];
		que.pop();
		for (int i = start; i < empty.size(); i++) {
			temp_table = setLine(table, empty[i][0], empty[i][1]);
			if (temp_table.empty()) continue;
			if (isSameEnd(temp_table)) return count;
			if (count + 1 > 3) continue;
			que.push(make_pair(temp_table, vector<int>{ count + 1, i + 1}));
		}
	}
	return -1;

}
int main() {
	//vector<vector<int>> table = makeTable();
	vector<vector<int>> table = makeTable2();
	vector<vector<int>> empty = emptyHorizon(table);
	//printTable(table);
	if (isSameEnd(table)) {
		cout << 0;
		return 0;
	}
	cout << BFS(table, empty);
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

9%를 도저히 못넘네요.. 도움!!

suyeony 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말