글 읽기 - 파이프 옮기기 질문입니다

pkc4913 4년 전 0

dp로 풀었습니다

dp[x][y][dir] : 파이프 끝의 위치가 (x,y)이고 이전 옮겨온 방향이 dir일때 나올 수 있는 경우의 수

로 정의해서 풀었습니다.

테스트케이스는 맞습니다

어디가 틀린걸까요?

#include<bits/stdc++.h>
using namespace std;

int dp[16][16][3];
int board[16][16];
int N;
int dx[3] = { 0,1,1 };
int dy[3] = { 1,0,1 };
int solve(int x, int y, int dir) {//오 아래 대
	if (x == N && y == N) return 1;
	int &ret = dp[x][y][dir];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = 0; i < 3; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 1 || ny < 1 || nx > N || ny > N) continue;
		if (dir == 0 && i == 1) continue; //오른쪽에서 왔으면 아래로 못감
		if (dir == 1 && i == 0) continue; //아래에서 왔으면 오른쪽으로 못감
		if (board[nx][ny]) continue; //벽있으면 못감
		if (i == 2) {
			if (board[x + dx[0]][y + dy[0]] || board[x + dx[1]][y + dy[1]]) continue;
		} //대각선으로 갈땐 3군데에 벽이 있는지 확인해줘야됨
		ret += solve(nx, ny, i);
	}
	return ret;
}
int main() {
	memset(dp, -1, sizeof(dp));
	cin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			scanf("%d", &board[i][j]);
	printf("%d", solve(1, 2, 0));
}

wjdclgns12 4년 전 1

집의 크기가 16인 경우가 입력으로 들어오면

board 배열에 어떤 식으로 저장되나요?

pkc4913 4년 전 0

아니 이런실수를... ㅠㅠ 감사합니다

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

문제

문제

출처

ICPC

파이프 옮기기 질문입니다

pkc4913 4년 전 0

wjdclgns12 4년 전 1

pkc4913 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말