탐욕스러운 재귀 검색

교수님은 그룹을 구성하는 다른 모든 지점에 대해 그리드의 특정 지점을 검색해야하는 과제를 주셨습니다 (이 예에서는 "L "문제의 모양).탐욕스러운 재귀 검색

그리드는 10x10이고 내 교수는 우리에게 시작점을주었습니다. 교수님은 우리에게 이웃 한 장소를 확인하고, 그 지점이 새로 발견되면 (세트에 포함될 것입니다) 그 세트에 그것을 추가하는 아이디어를주었습니다. 그런 다음 재귀 적으로 그 방법을 호출합니다.

private Spot findSpots(Set<Spot> spots, Set<Spot> activeSpots, Spot initial) { 
    Spot newSpot = null; 


    Set<Spot> activeSet = new HashSet<Spot>(); 
    checkAround(activeSet, new Spot(initial.i - 1, initial.j)); 
    checkAround(activeSet, new Spot(initial.i + 1, initial.j)); 
    checkAround(activeSet, new Spot(initial.i, initial.j - 1)); 
    checkAround(activeSet, new Spot(initial.i, initial.j + 1)); 


    for (Spot spot : activeSet) { 
     newSpot = findSpots(spots, activeSpots, spot); 
     if (grid[newSpot.i][newSpot.j] == true) 
      spots.add(newSpot); 
    } 

    return newSpot; 
} 
private boolean checkAround(Set<Spot> spots, Spot spot) { 
    if (!spots.contains(spot)) { 
     spots.add(spot); 
     return true; 
    } 
    return false; 
}

경계 조건이 필요합니다. 그렇지 않으면 stackoverflow 예외가 발생하지만 논리에 도움이 필요합니다. 내가 경계 조건을 필요로 알고

출처

2016-11-05 Kendrick Lamar

변수 이름에 더 많은 생각을하면 코드를 읽기 쉽고 수정하기가 쉽습니다. "initialSpots"와 같은 것조차도이 모든 다양한 스폿 구조를 추론하려고 할 때 훨씬 덜 혼란 스럽습니다. – dahui

I 다른 사람들이 쉽게 읽을 수 있도록 일부 변수의 이름을 변경했습니다. –

Spot 클래스에 부울 멤버 변수 또는 함수를 추가하거나 "hasBeenSearched"속성을 추가하고이 지점에서 이미 함수를 호출 한 경우 true로 설정하면 함수가 호출되지 않도록 할 수 있습니다. Spot.hasBeenSearched 만약 spot이 있다면 – dahui

는 [...]

당신은 스스로를 말했다. 하나의 핵심 단어는 경계입니다. 그리드에서 지점이 합법적인지 확인해야합니다 ( ). 그렇지 않은 경우 탐색을 중지해야합니다.

다른 정지 조건은 해당 지점이 이미 방문한 경우입니다.

이러한 두 가지 중지 조건을 구현하는 경우 및 추가 재귀 호출을하기 전에 이러한 검사를 수행하면 스택을 오버플로하지 않고도 해결책을 찾을 수 있습니다. 이 같은

뭔가 :

private int countSpots(Set<Spot> visited, Spot spot) { 
    if (!isValid(spot) || visited.contains(spot)) { 
     return 0; 
    } 

    visited.add(spot); 

    int count = 1; 
    count += countSpots(visited, new Spot(spot.x - 1, spot.y)); 
    count += countSpots(visited, new Spot(spot.x + 1, spot.y)); 
    count += countSpots(visited, new Spot(spot.x, spot.y + 1)); 
    count += countSpots(visited, new Spot(spot.x, spot.y - 1)); 
    return count; 
}

는 Btw은 당신이 사용하고있는 알고리즘은 은 위키 피 디아 페이지에서 더 많은 정보와 팁과 힌트를 참조 flood fill의 변형이다.

출처

2016-11-05 23:08:44 janos

당신은 나를 도와 줬습니다. 왜냐하면 당신이 어떤 종류의 algo인지 말해 주었기 때문에 나는 코드를 변경하고 끝낼 수있었습니다. –

그것이 내가했던 방법이었다 :

나는 내가 방문한 모든 지점을 포함하는 하나의 두 세트를했다 그리드
에 대한 경계 조건을 추가, 다른 하나는 내가
모두 이미
반환하는 경우
반복적으로 자리 주위에 모든 전화 적절한 세트에 지점을 추가

출처

2016-11-05 23:43:58

탐욕스러운 재귀 검색

답변

관련 문제