글 읽기 - 안녕하세요! dfs문제 질문이 있습니다

hd96dud 6년 전 0

안녕하세요! dfs문제 질문이 있습니다!

9%에서 틀렸습니다가 나오는데요

어디서 틀어진걸까요?

#include<cstdio>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;

string c[100];
string s;
int v[100][100];
int sum = 0;
int n, m, k, len;
int a[] = { -1, 1, 0, 0 };
int b[] = { 0, 0, -1, 1 };

void dfs(int x, int y, int node)
{
	if (node == len)
	{
		sum++; 
		return;
	}
	v[x][y] = 1; 
	for (int i = 1; i <= k; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			int mx = a[j] * i + x;
			int my = b[j] * i + y;
			if (mx < 0 || mx >= n || my < 0 || my >= m)
				continue;
			if(v[mx][my] == 0 && s[node] == c[mx][my])
				dfs(mx, my, node + 1);
		}
	}
	v[x][y] = 0;
}

int main()
{
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 0; i < n; i++)
		cin >> c[i];
	cin >> s;
	len = s.length();
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (c[i][j] == s[0])
				dfs(i,j,1);
	
	printf("%d\n", sum);
	return 0;
}

hd96dud 6년 전 0

자답합니다.. 문제를 확실하게 푼건 아니지만

중복의 허용이었군요. 몇시간을 고민한건지 참...

이미 썼던 문자도 쓸 수 있다는거였네요

vjerksen 6년 전 0

단순 백트래킹을 사용하면 시간초과가 납니다.

메모이제이션을 적용시켜보세요

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

문제

문제

출처

ICPC

안녕하세요! dfs문제 질문이 있습니다

hd96dud 6년 전 0

hd96dud 6년 전 0

vjerksen 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말