글 읽기 - 문자판 문제에 대해 질문드립니다

bs1010 5년 전 0

dp와 메모이제이션을 이용하여 풀이를 시도하였습니다. 혹시 어느부분에서 잘못되었는지 알 수 있을까요?

#include<stdio.h>// 문자판
#include<string.h>
char arr[105][105];
int dp[85][105][105];
char ans[85];//찾고 싶은 단어
int N = 0;//행
int M = 0;//열
int K = 0;//K개 칸 까지 이동가능
int back(int a, int b, int d) //a:행, b:열
{
	if (a < 0 || a >= N || b < 0 || b >= M)
		return 0;
	if (arr[a][b] != ans[d])
		return 0;
	if (dp[d][a][b] != 0)
		return dp[d][a][b];
	if (arr[a][b] == ans[d] && d==strlen(ans)-1)
	{
		dp[d][a][b] = 1;
		return dp[d][a][b];
	}
	for (int k = 1;k <= K;k++)
	{
		dp[d][a][b] = back(a + k, b, d + 1) + back(a - k, b, d + 1) + back(a, b + k, d + 1) + back(a, b - k, d + 1);
	}
	return dp[d][a][b];
}

int main(void)
{
	int sum = 0;
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0;i < N;i++)
		scanf("%s", &arr[i]);
	scanf("%s", ans);
	for (int i = 0;i < N;i++)
	{
		for (int j = 0;j < M;j++)
			sum += back(i, j, 0);

	}
	printf("%d \n", sum);
	return 0;
}

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

문제

문제

출처

ICPC

문자판 문제에 대해 질문드립니다

bs1010 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말