글 읽기 - 로직이 꼬였는지 정답이 나오질 않습니다.

pkc4913 4년 전 0

다음과 같은 점화식으로 풀었습니다.

dp[r1][c1][r2][c2][cnt] : (r1,c1)에서 (r2,c2)로 cnt만큼 이동해서 갈때 경로의 수

dp[r1][c1][r2][c2][cnt] = sum(dp[x1][y1][x2][y2][cnt - 2])

숏코딩 하신분들 보면 (코드는 안봤습니다) 이렇게 조잡하게 코드 안짜도 정답이 나오는거 같은데 접근법이 완전히 틀렸는지 잘 모르겠네요 ㅠㅠ

특히 재귀함수 기저사례에서 조건처리를 어떻게 할지 잘 모르겠습니다

힌트라도 주실수 있나요??

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

int dp[21][21][21][21][21];
int A[21][21];
int N,L;
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
int solve(int r1, int c1, int r2, int c2, int cnt) {
	if (cnt == 0) { //이동가능횟수가 0이면 반드시 제자리여야한다.
		if (r1 == r2 && c1 == c2) return 1;
		else return 0;
	}
	if (cnt == 1) { //이동가능횟수가 1이면 반드시 인접한(8방향)곳에 있어야한다 
		for (int i = 0; i < 8; i++) {
			int nx1 = r1 + dx[i];
			int ny1 = c1 + dy[i];
			if (nx1 <= 0 || ny1 <= 0 || nx1 > N || ny1 > N) continue;
			if (nx1 == r2 && ny1 == c2) {
				if (A[r1][c1] == A[r2][c2]) return 1;
			}
		}
		return 0;
	}
	int &ret = dp[r1][c1][r2][c2][cnt];
	if (ret != -1) return ret;
	ret = 0;
	for (int i = 0; i < 8; i++) {
		int nx1 = r1 + dx[i];
		int ny1 = c1 + dy[i];
		if (nx1 <= 0 || ny1 <= 0 || nx1 > N || ny1 > N) continue;
		for (int j = 0; j < 8; j++) {
			int nx2 = r2 + dx[j];
			int ny2 = c2 + dy[j];
			if (nx2 <= 0 || ny2 <= 0 || nx2 > N || ny2 > N) continue;
			if (A[nx1][ny1] == A[nx2][ny2]) {//양끝이 같은수면 이어주고 이동가능횟수를 2줄인다
				ret += solve(nx1, ny1, nx2, ny2, cnt - 2);
			}
		}
	}
	return ret;
}
int main() {
	cin >> N >> L;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			scanf("%d", &A[i][j]);
	memset(dp, -1, sizeof(dp));
	int ans = 0;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			for (int k = 1; k <= N; k++)
				for (int w = 1; w <= N; w++)
					if (A[i][j] == A[k][w]) ans += solve(i, j, k, w, L);
	printf("%d", ans);
}

sait2000 4년 전 0

경로의 길이가 L일때 움직이는 회수가 L번인가요?

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

문제

문제

출처

ICPC

로직이 꼬였는지 정답이 나오질 않습니다.

pkc4913 4년 전 0

sait2000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말