글 읽기 - 어디가 틀린건지 잘 모르겠습니다ㅜㅜ

psjinqkr 5년 전 0

어디가 틀린건지 잘 모르겠습니다ㅜㅜ

#include<iostream>

using namespace std;

int n, l, ans;
int board[100][100];
void dfs1(int r, int c);
void dfs2(int r, int c);
int main() {
	cin >> n >> l;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	}
	ans = 0;
	
	for (int i = 0; i < n; i++) {
		dfs1(i, 0);
	}
	for (int i = 0; i < n; i++) {
		dfs2(0, i);
	}
	cout << ans;
	system("pause");

}

bool check(int r, int c) {
	if (r >= 0 && r < n&&c >= 0 && c < n)
		return true;
	return false;
}

//dfs1 왼쪽에서 오른쪽으로 
//현재 위치에서 두가지 선택 가능
//1) 같은높이면 이동
//2) l칸동안 같은높이이고 ㅣ+1칸은 높이가 1차이여야한다
void dfs1(int r, int c) {
	if (c == n - 1) {
		ans++;
		return;
	}
	for (int i = 0; i < 2; i++) {
		if (i == 0) {
			if (check(r, c + 1) && board[r][c] == board[r][c + 1]) {
				dfs1(r, c + 1);
			}
		}
		else if (i == 1) {
			bool ch = true;
			for (int j = 1; j < l; j++) {
				if (check(r, c + j) && board[r][c] != board[r][c + j])
					ch = false;
				if (check(r, c - j) && board[r][c] != board[r][c - j])
					ch = false;
			}
			if (ch&&check(r, c + l)){
				if (board[r][c] - board[r][c + l] == 1 || board[r][c] - board[r][c + l] == -1) {
					
					dfs1(r, c + l);
				}
			}
		}
	}
	return;
}
//dfs2 위에서 아래로
// 현재위치에서 두가지 선택 가능
//1) 같은 높이면 이동
//2) l칸동안 같은높이이고 l+1칸은 높이가 1차이여야한다.
void dfs2(int r, int c) {
	if (r == n - 1) {
		ans++;
		return;
	}
	for (int i = 0; i < 2; i++) {
		if (i == 0) {
			if (check(r+1, c ) && board[r][c] == board[r+1][c ]) {
				dfs2(r+1, c);
			}
		}
		else if (i == 1) {
			bool ch = true;
			for (int j = 1; j < l; j++) {
				if (check(r+j, c ) && board[r][c] != board[r+j][c])
					ch = false;
				if (check(r-j, c) && board[r][c] != board[r-j][c])
					ch = false;
			}
			if (ch&&check(r+l, c )){
				if (board[r][c] - board[r + l][c] == 1 || board[r][c] - board[r + l][c] == -1) {
					dfs2(r + l, c);
				}
			}
		}
	}
	return;
}

so6275 5년 전 0

설계자체를 잘못하신거같아요

dfs로 진행하면서 높이가 같으면 무조건 갈 수 있고

높이가 낮다면 차이가 1이어야하고 그 지점부터 l만큼 거리가 다 같아야 갈 수 있고, 그 거리만큼은 memorization해줘야합니다. 그 이유는

높이가 크다면 차이가 1이어야하고 그 전지점부터 l만큼 거리 전까지가 다 같아야하고 + 이미 설치되지 않은곳이어야합니다.

예를 들어서

333222333일때 l =2이면 333(2)(2)2333 (괄호친부분은 다리를 이미 설치한곳) 인 경우 (2)(2)2이기 때문에 높은곳으로 올라갈때 경사로를 설치할 수 없습니다.

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

문제

문제

출처

ICPC

어디가 틀린건지 잘 모르겠습니다ㅜㅜ

psjinqkr 5년 전 0

so6275 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말