글 읽기 - 어떤 부분을 놓치고 있는걸까요??

dmsrb1002 5년 전 0

dp를 이용해서 생각해봤습니다.

x,y좌표,현재까지 탐색한 string s와 찾고자하는 문자열(TARTU)의 인덱스인 idx를 재귀 인자로 사용했습니다.

아래는 재귀함수 부분입니다.

int dy[] = { -1,0,1,1,1,0,-1,-1 };
int dx[] = { -1,-1,-1,0,1,1,1,0 };
int dp[101][201][201];    //x좌표,y좌표,string의 size
bool visited[101][201][201];
int go(int x, int y, string s, int idx)
{

	if (s == word)return 1;
	if (visited[x][y][s.size()])return 0;
	visited[x][y][s.size()]=true;
	int& ret = dp[x][y][s.size()];
	if (ret != -1)return dp[x][y][s.size()];
	ret = 0;
	for (int i = 0; i < 8; ++i)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && nx < H && ny >= 0 && ny < W)
		{
			if (A[nx][ny] == word[idx])
			{
				ret+= go(nx, ny, s + A[nx][ny], idx + 1);
			}
			else
			{

				ret += go(nx, ny, s, idx);
			}
		}
	}
	return ret;

}

kimsy96 5년 전 0

아직 풀어보지 않았지만 하나 걸리는게 있다면

10¹⁸ 는 int범위로 나타낼 수 없겠죠

dmsrb1002 5년 전 0

네 맞습니다.

하지만 제가 작성한 코드는 주어진 예제조차 맞지 않는걸로보아 범위형이외의 다른 문제인것 같습니다.

흠..

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

문제

문제

출처

ICPC

어떤 부분을 놓치고 있는걸까요??

dmsrb1002 5년 전 0

kimsy96 5년 전 0

dmsrb1002 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말