글 읽기 - [15684 사다리조작] 틀렸습니다.(반례를 요청드립니다.)

vjavm7986 5년 전 0

사다리 왼쪽 부분을 1, 오른쪽 부분을 2로 표기하여 사다리를 두는 방식을 사용하였습니다.

dfs 재귀로 진행을 했는데 예시는 다 맞는데 틀렸다고 나와서

어떤 반례가 있는지 도움을 요청드리고자 합니다.

감사합니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, h;
int minVal = 99999;

void dfs(vector<vector<int> > a, int index, int cnt, vector<pair<int,int> > ladder){
	if(cnt > 3) return ;
		
	int cx;
	int cy;
	int next;
	for(int i = 1 ; i <= n ; i++){
		cx = i;
		cy = 1;
		while(cy <= h) {
			if(a[cy][cx] == 1) {
				cx += 1;
			} else if(a[cy][cx] == 2) {
				cx -= 1;	
			}
			cy++;
		}
		
		if(i == cx) {
			next = i + 1;			
			continue;
		}
		else {
			cx = i;
			break;
		}
	}
	if(next == n + 1) {
		if(cnt < minVal) minVal = cnt;
		return;
	}
	
	vector<vector<int> > b(h + 1, vector<int>(n + 1));
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= n ; j++){
			b[i][j] = a[i][j];
		}
	}	
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j < n ; j++){
			if(b[i][j] == 0 && b[i][j+1] == 0){
				b[i][j] = 1;
				b[i][j+1] = 2;
				vector<pair<int,int> > new_ladder;
				new_ladder = ladder;
				new_ladder.push_back(make_pair(i,j));
				dfs(b, cx + 1, cnt + 1, new_ladder);
				b[i][j] = 0;
				b[i][j+1] = 0;
			}
		}		
	}
	return;	
}

int main(){
	
	cin >> n >> m >> h;
	
	vector<vector<int> > a(h + 1, vector<int>(n + 1));
	
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= n ; j++){
			a[i][j] = 0;
		}
	}
	
	int ladder_x, ladder_y;
	for(int i = 0 ; i < m ; i++){
		cin >> ladder_x >> ladder_y;
		a[ladder_x][ladder_y] = 1;
		a[ladder_x][ladder_y + 1] = 2;
	}
	
	vector<pair<int,int> > ladder;
	dfs(a, 1, 0, ladder);

	if(minVal == 99999) minVal = -1;

	cout << minVal;
	
	return 0;	
}

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

문제

문제

출처

ICPC

[15684 사다리조작] 틀렸습니다.(반례를 요청드립니다.)

vjavm7986 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말