글 읽기 - 15684 사다리 문제 반례 부탁 드립니다 ㅠㅠ

ji5u1031 5년 전 0

주어진 예제와 질문에 있는 몇몇 반례들은 모두 시도했지만 맞았습니다.

하지만 제출하면 틀렸습니다 뜨네요 ㅠㅠ

어떤 반례에서 틀리는지 모르겠습니다 ㅠㅠ

고수님들의 소중한 의견 부탁드립니다!

감사합니다!

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

//두 선이 인접하거나 서로 접하면 안된다.
const int NMAX = 10;
const int HMAX = 30;
bool map[HMAX + 4][NMAX + 4] = {0,}; 

int N, M, H;

void printmap(){
	for(int i = 1; i <= H ; i++){
		for(int k =1;  k <= N; k++) cout << map[i][k] << " ";
		cout<<endl;
	}
	cout<<"----------------------------"<<endl;
}
int lr[2] = {-1,1};
int go(int y){
	int x = 1;
	while(x <= H + 1){
		int leftright = -1;
		
		if(map[x][y-1]) leftright = 0;
		
		if(map[x][y]) leftright = 1;
		
		if(leftright >= 0){
			y += lr[leftright];
		}
		x++;
	}
	return y;
}

bool check_same(){
	for(int i = 1; i <= N; i++){
		if(i != go(i)) return false;
	}
	return true;
}

int minimum = 4;

void DFS(int x, int y, int depth){
	//기저 조건 
	if(x > H || y >= N) return; // 범위 설정 
	if(depth > 3) return; //사다리 추가 개수가 3 초과이면 의미 없다 
	if(depth >= minimum) return; //이미찾은 최소값보다 크다면 의미 없다 
	//printmap();
	if(check_same()){
		minimum = min(minimum, depth);
	}
	
	if(y < N - 1){// 열 한칸 이동 
		if(!map[x][y] && !map[x][y-1] && !map[x][y+1]){ 
			map[x][y] = true;
			DFS(x,y+1,depth+1);
			map[x][y] = false;
			DFS(x,y+1,depth);
		}else{
			DFS(x,y+1,depth);
		}
	}
	else if ( y == N - 1){ //마지막 열이라면 행 이동 
		if(!map[x][y] && !map[x][y-1] && !map[x][y+1]){
			map[x][y] = true;
			DFS(x + 1,1,depth+1);
			map[x][y] = false;
			DFS(x + 1, 1, depth);
		}else{
			DFS(x + 1, 1, depth);
		}
	}
}

int main(){
	cin >> N >> M >> H; // N: 세로선의 수 H: 다리의 수 M: 가로선의 수 
	for(int i = 0; i < M; i++){
		int a, b;
		cin >> a >> b;
		map[a][b] = true;
	}

	
	DFS(1,1,0);
	if(minimum > 3) minimum = -1;
	
	cout<<minimum << endl;
	
	return 0;
}

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

문제

문제

출처

ICPC

15684 사다리 문제 반례 부탁 드립니다 ㅠㅠ

ji5u1031 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말