가능한 모든 경로 찾기

Question

가능한 모든 경로를 찾는 데 문제가 있습니다.

A A A B A B

A A

A B 점에서 2,3- 종료 0,0 시작점에서 여행

B. 가능한 모든 경로를 가져와야합니다. 내가 할 수있는

가능한 이동 잘 이동 및 을 아래로 이동합니다.

내가 어디에 갇혀 있는지 말해 보겠습니다. 재귀 함수를 사용하려고합니다. 0,0 점을 시작으로 할 수있을 때마다 오른쪽으로 이동하고 필연적으로 내려야합니다.

내 재귀 함수 내 순환 이동 기능에 대한

public static move(int i,int j) 
{ 
    if(possible(x,y+1)) 
    { 
     move(x,y+1); 
     move(x+1,y); 
    } 

} 


public static bool possible(int i,int j) 
     { 
      if((i >=0 && i<3) && (j>=0 && j<4)) 
       return true; 
      else 
       return false; 

     } 

확실하지. 여전히 그것을 확장해야합니다. 나는 내가 어떻게 구현해야하는지 정확히 알지 못한다.

이동 메소드를 사용하여 코너 노드까지 이동할 수 있지만 코너 상단 오른쪽 포인트 (0,4)에서 가능한 모든 이동에 도달 할 때마다 해당 함수를 다시 추적해야합니다.

Answer 1

public void MoveUp(Object sender, MoveEventArgs e) 
    { 
     if (CanMoveUp(e.CurrentPosition.Y)) ... 
    } 
    public void MoveDown(Object sender, MoveEventArgs e) 
    { 
     if (CanMoveDown(e.CurrentPosition.Y)) ... 
    } 
    public void MoveLeft(Object sender, MoveEventArgs e) 
    { 
     if (CanMoveLeft(e.CurrentPosition.X)) ... 
    } 
    public void MoveRight(Object sender, MoveEventArgs e) 
    { 
     if (CanMoveRight(e.CurrentPosition.X)) ... 
    } 
    private bool CanMoveUp(double y) => (y - 1) > 0; 
    private bool CanMoveDown(double y) => (y + 1) < 4; 
    private bool CanMoveLeft(double x) => (x - 1) > 0; 
    private bool CanMoveRight(double x) => (x + 1) < 4; 

이 값은 맞지 않을 수 있지만, 코드를 재사용하고 쉽게 각각의 방법에 추가를 추가 할 수 있습니다 움직임에 다른 가능한 장벽을 추가 할 것입니다 경우에 쉽게 유지 보수입니다.

Answer 2

팜을 포기하고 도움이되지 않습니다. 당신은 3 개 경계 기능

로 결정 로직을 분해한다

inBoundsX x 
    // return true if x is in bounds, false otherwise 

inBoundsY y 
    // return true if y is in bounds, false otherwise 

inBoundsXY x,y 
    // return true if x and y are in bounds, false otherwise 

항상 다음, 그것은 주어진 것 초기 상태를 확인 다음 이동하는 방법을 결정해야합니다 귀하의 재귀 함수.

move x,y 
    if inBoundsXY x,y 
     print I am here x,y 
     // use InboundsX, InboundsY to decide next move. 

Answer 3

큰 걸음을 뒤로 옮겨야합니다.

첫 번째 단계는 메소드의 서명이 있어야합니다. 문제는 무엇입니까?

가능한 모든 경로를 언급하지

찾기 : 좌표 특정 시작.

그래서 방법은 경로의 세트 반환해야 : 지금 우리는 어딘가에 얻고

static Set<Path> AllPaths(Coordinate start) { /* a miracle happens */ } 

확인을; 이제 우리에게 필요한 것이 분명 해졌습니다. 우리는 일련의 것들을 필요로하고, 우리는 길을 필요로하며, 우리는 좌표가 필요합니다.

좌표 란 무엇입니까?한 쌍의 정수 :

완료. 그래서 스택을 팝하십시오. 어떤 경로입니까? 경로는 비어 있거나 경로 뒤에 오는 첫 번째 단계가 될 수 있습니다.

sealed class Path 
{ 
    private Path() { } 
    private Path(Coordinate first, Path rest) 
    { 
    this.first = first; 
    this.rest = rest; 
    } 
    public static readonly Path Empty = new Path(); 
    private Coordinate first; 
    private Path rest; 
    public bool IsEmpty => this == Empty; 
    public Coordinate First 
    { 
    get 
    { 
     if (this.IsEmpty) throw new Exception("empty!"); 
     return first; 
    } 
    } 
    public Path Rest 
    { 
    get 
    { 
     if (this.IsEmpty) throw new Exception("empty!"); 
     return rest; 
    } 
    } 
    public Path Append(Coordinate c) => new Path(c, this); 
    public IEnumerable<Coordinate> Coordinates() 
    { 
    var current = this; 
    while(!current.IsEmpty) 
    { 
     yield return current; 
     current = current.Rest; 
    } 
    } 
} 

완료.

이제 Set<T>을 구현합니다. "모든 항목"및 "이 항목을 다른 항목과 조합하여 세 번째 항목을 생성하는 작업"이 필요합니다. 세트가 불변인지 확인하십시오.. 새 항목을 추가 할 때 세트를 변경하고 싶지는 않습니다. 당신은 다른 세트를 원한다. 1을 추가 할 때 3을 4로 변경하지 않는 것과 같은 방식입니다. 3과 4는 다른 숫자입니다.

이제 실제로 문제를 해결하는 데 필요한 모든 도구가 제공됩니다. 이제 구현할 수 있습니다

static Set<Path> AllPaths(Coordinate start) 
{ 
    /* a miracle happens */ 
} 

어떻게 작동하나요? 모든 재귀 함수가 같은 형태를 가질 것을 기억하십시오 :

• 우리가 사소한 경우가 아니라면, 사소한 경우
• 해결 재귀 적으로 그것을 해결, 작은 케이스에 문제를 줄이고, 솔루션을 결합합니다.

그렇다면 간단한 사례는 무엇입니까?

static Set<Path> AllPaths(Coordinate start) 
{ 
    /* Trivial case: if the start coordinate is at the end already 
     then the set consists of one empty path. */ 

은을 구현합니다.

재귀 사례는 무엇입니까?

/* Recursive case: if we're not at the end then either we can go 
     right, go down, or both. Solve the problem recursively for 
     right and/or down, union the results together, and add the 
     current coordinate to the top of each path, and return the 
     resulting set. */ 

구현하십시오. 여기

교훈은 다음과 같습니다 등등 설정, 경로, 좌표, 그리고 :

• 모든 문제에서 명사의 목록을 확인합니다.
• 각 유형을 나타내는 유형을 지정하십시오. 단순하게 유지하고 각 유형에 필요한 작업을 정확히 구현하는지 확인하십시오.
• 이제 각각의 명사에 대해 추상화를 구현 했으므로 추상화를 사용하는 알고리즘을 설계 할 수 있습니다.
• 재귀의 기본 규칙을 기억하십시오. 가능한 경우 기본 사례를 해결하십시오. 그렇지 않은 경우 작은 재귀 사례를 해결하고 솔루션을 결합합니다.