글 읽기 - 제발 한번만 봐주세요!! 한번만 도와주세요!!!!

smu04129 3년 전 0

방문체크 함수는 자기자신과 좌우 연속된 곳에 전부 표시를 해줍니다.

먼저 이미 연결된 사다리 좌표 받을때 거기서도 방문체크해주고

전체 사다리 놓을수 있을 좌표를 따로 coord에 저장해준뒤

coord 인덱스 번호 조합으로 뽑아서

check()로 검사해줍니다.

9프로 에서 시간초과 뜨는데 미치겠네요..

제발 도움을 주세요..

#include <iostream>
#include <vector>
using namespace std;

typedef pair<int, int> pii;

int n, m, h, num = 1, answer = 987654321;
vector<vector<int>> map;
vector<vector<bool>> visit;
vector<pii> coord;

void visited(int y, int x) { 
	visit[y][x - 1] = true, visit[y][x] = true, visit[y][x + 1] = true; 
}

void unvisit(int y, int x) { 
	visit[y][x - 1] = false, visit[y][x] = false, visit[y][x + 1] = false;
}

inline bool check() {
	/*cout << "\n";
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= n; j++) { cout << map[i][j] << " "; }
		cout << "\n";
	}
	cout << "\n";*/
	for (int j = 1; j <= n; j++) {
		int k = j;
		for (int i = 1; i <= h; i++) {
			//cout << k << " -> ";
			if (map[i][k] != 0) {
				if (k > 1 && map[i][k] == map[i][k - 1]) { k--; }
				else if (k < n && map[i][k] == map[i][k + 1] ) { k++; }
			}
			//cout << k << "\n";
		}
		//cout << "\n";
		if (k != j) { return false; }
	}
	return true;
}

void dfs(int cnt, int idx) {
	//cout << "cnt: " << cnt << "\n";
	if (cnt > 3 || cnt > answer) { return; }
	if(check() && answer > cnt) { answer = cnt; return; }
	for (int i = idx; i < coord.size(); i++) {
		if (visit[coord[i].first][coord[i].second]) { continue; }
		//cout << coord[i].first << " " << coord[i].second << " ";
		map[coord[i].first][coord[i].second] = num;
		map[coord[i].first][coord[i].second + 1] = num++;
		visited(coord[i].first, coord[i].second);
		dfs(cnt + 1, i + 1);
		unvisit(coord[i].first, coord[i].second);
		map[coord[i].first][coord[i].second + 1] = 0;
		map[coord[i].first][coord[i].second] = 0;
		num--;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> h;
	map.resize(h + 1, vector<int>(n + 1, 0));
	visit.resize(h + 1, vector<bool>(n + 1, false));
	for (int i = 0; i < m; i++) {
		int y, x;
		cin >> y >> x;
		visited(y, x);
		map[y][x] = num, map[y][x + 1] = num++;
	}
	for (int i = 1; i <= h; i++)
		for (int j = 1; j < n; j++)
			if (!visit[i][j]) { coord.push_back({ i, j }); }
	if (check()) { cout << 0; return 0; }
	dfs(0, 0);
	if (answer == 987654321) { cout << -1; }
	else { cout << answer; }
}

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

문제

문제

출처

ICPC

제발 한번만 봐주세요!! 한번만 도와주세요!!!!

smu04129 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말