글 읽기 - 하향식과 상향식...

windowline1206 6년 전 0

출발점에서 목적지로 도달하는 방식과

목적지에서부터 출발점을 추적하는 방식... 중 질문 있씁니다.

int vcnt(int y, int x)
{
	if (y == m-1 && x == n-1)
		return 1;
	
	if (cache[y][x] != -1)return cache[y][x];

	cache[y][x] = 0;

	for (int p = 0; p < 4; p++)
	{
		int ny = y + my[p];
		int nx = x + mx[p];
		if (nx >= 0 && nx < n  &&  ny >= 0 && ny < m && grid[ny][nx] < grid[x][y])
			cache[y][x] += vcnt(ny, nx);
	}
	return cache[y][x];
}

이렇게 하고 cout << vcnt(0, 0) << endl를 하면 답이 나옵니다. 
   ( vcnt(y, x): y, x부터 m-1, n-1까지 가는 경우의 수 )
    
    
   하지만
   
   
   int vcnt(int y, int x)
{
	if (y == 0 && x == 0)
		return 1;
	
	if (cache[y][x] != -1)return cache[y][x];

	cache[y][x] = 0;

	for (int p = 0; p < 4; p++)
	{
		int ny = y + my[p];
		int nx = x + mx[p];
		if (nx >= 0 && nx < n  &&  ny >= 0 && ny < m && grid[ny][nx] > grid[x][y])
			cache[y][x] += vcnt(ny, nx);
	}
	return cache[y][x];
}
  이렇게하고 cout << vcnt(m-1, n-1) << endl; 를하면 틀립니다. ㅠㅠ
        (여기서 vcnt(y, x): 0,0 에서 y, x까지 가는 경우의 수 )라고 생각하는데...
      
 추정되는 원인은 캐쉬를 즉각즉각 더해주는 것 떄문인것 같기도합니다만..
 즉시 더해주지 않으면 중복된 방문 떄문인지 무한루프가 나더군요...
 
 현기증납니다... 도와주세요
    

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

문제

문제

출처

ICPC

하향식과 상향식...

windowline1206 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말