C++ 간단하지만 해결할 수 없습니까? 난 안

Question

하자 T (X, Y)가 × X를 통해 투어의 숫자 생각 Y 그리드하도록 : 투어는

투어는 이동 구성 왼쪽 상단 광장에서 시작

1. 위로, 아래로, 왼쪽으로 또는 오른쪽으로 사각형
2. 투어는 각 사각형을 정확히 한 번 방문합니다.
3. 둘러보기는 왼쪽 하단 정사각형으로 끝납니다.

예를 들어 T (2,2) = 1, T (3,3) = 2, T (4,3) = 0 및 T (3,4) = 4. T (10,4)을 계산하는 프로그램을 작성하십시오.

나는 몇 시간 동안이 작업을 해왔다 ... 그리드의 크기를 입력으로 받아들이고 가능한 둘러보기의 수를 반환하는 프로그램이 필요합니까?

나는 몇 시간 동안이 작업을 해왔다 ... 그리드의 크기를 입력으로 받아들이고 가능한 둘러보기의 수를 반환하는 프로그램이 필요합니까?

이 문제를 해결하기 위해이 코드를 작성했습니다 ... 모든 방향을 검사하는 방법을 찾는 것 같습니다.

#include <iostream> 

int grid[3][3]; 
int c = 0; 

int main(){  
    solve (0, 0, 9); 
} 

int solve (int posx, int posy, steps_left){ 
    if (grid[posx][posy] = 1){ 
     return 0; 
    } 
    if (steps_left = 1 && posx = 0 && posy = 2){ 
     c = c+1; 
     return 0; 
    } 
    grid[posx][posy] = 1; 
    // for all possible directions 
    { 
     solve (posx_next, posy_next, steps_left-1) 
    } 
    grid[posx][posy] = 0; 
} 

이 알고리즘은 @KarolyHorvath 에 의해 당신은 그리드 (/ 방문 방문하지)에 세포의 상태를 표현하기 위해 몇 가지 데이터 구조가 필요합니다.

알고리즘 :

step(posx, posy, steps_left) 
    if it is not a valid position, or already visited 
     return 
    if it's the last step and you are at the target cell 
     you've found a solution, increment counter 
     return 
    mark cell as visited    
    for each possible direction: 
     step(posx_next, posy_next, steps_left-1) 
    mark cell as not visited 

및 단계를 실행 (0, 0, SIZEX * SIZEY)는 알고리즘을받은 적이 있기 때문에 그것은, 어렵지 않다

Answer 1

. 이 문제를 해결하려면 동적 데이터 구조가 필요할 것입니다 (T (10,4)의 정확한 경우에만 관심이있는 경우 제외). 나머지는 y 방향의 숫자가 일 때 왼쪽이 -1, 오른쪽이 +1이고 아래쪽이 -1입니다. 방문한 경계 검사 및 확인을 추가하면 작업이 완료됩니다.

하지만 분명한 알고리즘이 얼마나 걸릴지 궁금합니다. 각 셀에 대해 4 방향 결정이있는 이 있습니다. T (10,4)의 40 개 셀들에 대해, 그것은 4^40의 결정 인 입니다. 타당성이 없다. 을 제거하는 것과 같은 것들이 이미 셀을 방문하고 범위 검사를 통해 많은 분기를 제거하지만, 여전히 ... 경쟁의 목표는 알고리즘을 찾는 것일 수 있습니다.

Answer 2

디버거를 선택하고 작은 보드 (2x2, 3x3)에서 진행중인 작업을 확인해야합니다.

하나의 명백한 문제는 비교가 아닌 =이 할당 일 것입니다. 비교 대상 : ==.

더 많은 문제가 있습니다. 그들을 찾아라.