(Actionscript 3) 2 차원 배열에서 스택 오버플로를 수정하는 방법은 무엇입니까?

Question

내 프로그램에서 2 차원 배열의 두 위치는 동등한 정수의 경로가있는 경우 두 위치를 연결하기 위해 따라갈 수있는 것으로 간주됩니다. 예를 들어,

[2, 2, 0, 0, 0 
    0, 2, 1, 1, 0 
    0, 2, 1, 0, 0 
    0, 0, 1, 2, 0 
    0, 1, 1, 0, 0] 

배열 [4] [1]과 배열은 약 이동 이후 [1] [3]에 접속 간주된다 [4] [1] [1] [3]의 경로를 따라 1이야. 그러나 [0] [0]은 [2]의 경로가 없기 때문에 [3] [3]에 연결되지 않습니다.이 위치 중 하나에서 다른 위치로 이동할 수 있습니다. 동등한 정수의 경로 만 따라갈 수 있습니다.

위치가 연결되어 있는지 여부를 확인하는 코드입니다. isConnectedTo (4, 1, 1, 3)는 [4] [1]과 [1] [3]이 연결되어 있는지 확인해야합니다. isConnectedTo (0, 0, 3, 3)는 [0] [0]과 [3] [3]이 연결되어 있는지를 확인합니다.

function isConnectedTo(i1: int, j1: int, i2: int, j2: int): Boolean{ 
if(i1==i2 && j1==j2){ 
    return true; 
} 
if(boardArray[i1][j1]!=boardArray[i2][j2]){ 
    return false; 
} 
if(boardArray[i1][j1]==0 || boardArray[i2][j2]==0){ 
    return false; 
} 
if(j1==j2 && Math.abs(i1-i2)==1){ 
    return true; 
} 
if(i1==i2 && Math.abs(j1-j2)==1){ 
    return true; 
} 
if(i2-1>=0 && boardArray[i2-1][j2]==boardArray[i2][j2] && isConnectedTo(i1, j1, i2-1, j2)){ 
    return true; 
} 
if(i2+1<boardArray.length && boardArray[i2+1][j2]==boardArray[i2][j2] && isConnectedTo(i1, j1, i2+1, j2)){ 
    return true; 
} 
if(j2-1>=0 && boardArray[i2][j2-1]==boardArray[i2][j2] && isConnectedTo(i1, j1, i2, j2-1)){ 
    return true; 
} 
if(j2+1<boardArray[0].length && boardArray[i2][j2+1]==boardArray[i2][j2] && isConnectedTo(i1, j1, i2, j2+1)){ 
    return true; 
} 
return false; 
} 

그러나이 코드는 스택 오버플로를 발생시킵니다. 이 문제를 쉽게 해결할 수 있습니까? 고마워, 내가 얻을 수있는 도움을 주셔서 감사합니다.

편집 : 좋아, 나는 당신이 제안한 것과 같은 패스 파인더 같은 것을 사용했다. 함수가 "true"를 throw 할 때마다 게임이 느려지는 것을 제외하고는 완벽하게 작동합니다. 내가 제대로하고 있니?

function isConnectedTo(i1: int, j1: int, i2: int, j2: int): Boolean{ 
    for(var i:int=0; i<boardArray.length; i++){ 
     for(var j:int=0; j<boardArray[i].length; j++){ 
      counterValues[i][j]=-1; 
     } 
    } 
    counterValues[i2][j2]=0; 
    setCounterValues(i2, j2); 
    return counterValues[i1][j1]>=0; 
} 
function setCounterValues(i:int, j:int): void{ 
    if(boardArray[i][j]==0){ 
     return; 
    } 
    if((i-1<0 || boardArray[i-1][j]!=boardArray[i][j] || counterValues[i-1] 
[j]!=-1) 
     &&(j-1<0 || boardArray[i][j-1]!=boardArray[i][j] || counterValues[i 
][j-1]!=-1) 
     &&(i+1>=boardArray.length || boardArray[i+1][j]!=boardArray[i][j] || 
counterValues[i+1][j]!=-1) 
     &&(j+1>=boardArray[i].length || boardArray[i][j+1]!=boardArray[i][j] 
|| counterValues[i][j+1]!=-1)){ 
     return; 
    } 
    if(i-1>=0 && boardArray[i-1][j]==boardArray[i][j] && counterValues[i-1] 
[j]==-1){ 
     counterValues[i-1][j]=counterValues[i][j]+1; 
     setCounterValues(i-1, j); 
    } 
    if(j-1>=0 && boardArray[i][j-1]==boardArray[i][j] && counterValues[i][j- 
1]==-1){ 
     counterValues[i][j-1]=counterValues[i][j]+1; 
     setCounterValues(i, j-1); 
    } 
    if(i+1<boardArray.length && boardArray[i+1][j]==boardArray[i][j] && 
counterValues[i+1][j]==-1){ 
     counterValues[i+1][j]=counterValues[i][j]+1; 
     setCounterValues(i+1, j); 
    } 
    if(j+1<boardArray[i].length && boardArray[i][j+1]==boardArray[i][j] && 
counterValues[i][j+1]==-1){ 
     counterValues[i][j+1]=counterValues[i][j]+1; 
     setCounterValues(i, j+1); 
    } 
} 

Answer 1

나는 함수의 시작 부분이 추가 :이 때문에

isConnectedTo: (4,1), (1,2) 
isConnectedTo: (4,1), (2,2) 
isConnectedTo: (4,1), (1,2) 
isConnectedTo: (4,1), (2,2) 
isConnectedTo: (4,1), (1,2) 

가 isConnectedTo 알고리즘은 무한 루프를 실행 : 다음과 같은 출력을 산출 trace("isConnectedTo: (" + i1 + "," + j1 + "), ("+ i2 + "," + j2 + ")");

주어진 위치를 이미 확인했는지 알 길이 없습니다.

이 문제를 해결하기위한 한 가지 방법은 이전 좌표를 함수 호출에 추가하고 방금 도착한 위치를 다시 확인하는 경우 재귀를 단락하는 것입니다. 재귀 적으로 포함 된 행에있는 m+/-1 != n 양식의 검사에 유의하십시오 통화) :

private function isConnectedTo(i1: int, j1: int, i2: int, j2: int, i3:int = -1, j3:int = -1): Boolean { 
    trace("isConnectedTo: (" + i1 + "," + j1 + "), ("+ i2 + "," + j2 + ")"); 
    if(i1==i2 && j1==j2){ 
     return true; 
    } 
    if(boardArray[i1][j1]!=boardArray[i2][j2]){ 
     return false; 
    } 
    if(boardArray[i1][j1]==0 || boardArray[i2][j2]==0){ 
     return false; 
    } 
    if(j1==j2 && Math.abs(i1-i2)==1){ 
     return true; 
    } 
    if(i1==i2 && Math.abs(j1-j2)==1){ 
     return true; 
    } 
    //Up 1 square 
    if(i2-1>=0 && (i2-1 != i3) && boardArray[i2-1][j2]==boardArray[i2][j2] && isConnectedTo(i1, j1, i2-1, j2, i2, j2)){ 
     return true; 
    } 
    //Down 1 square 
    if(i2+1<boardArray.length && (i2+1 != i3) && boardArray[i2+1][j2]==boardArray[i2][j2] && isConnectedTo(i1, j1, i2+1, j2, i2, j2)){ 
     return true; 
    } 
    //Left 1 square 
    if(j2-1>=0 && (j2-1 != j3) && boardArray[i2][j2-1]==boardArray[i2][j2] && isConnectedTo(i1, j1, i2, j2-1, i2, j2)){ 
     return true; 
    } 
    //Right 1 square 
    if(j2+1<boardArray[0].length && (j2+1 != j3) && boardArray[i2][j2+1]==boardArray[i2][j2] && isConnectedTo(i1, j1, i2, j2+1, i2, j2)){ 
     return true; 
    } 
    return false; 
} 

또 다른 방법은 메모 -이지는 수표에 있습니다 :

private var visited:Dictionary = new Dictionary();   

private function isConnectedTo(i1: int, j1: int, i2: int, j2: int): Boolean { 
    var statusKey:String = i2 + "_" + j2; 
    trace("isConnectedTo: (" + i1 + "," + j1 + "), ("+ i2 + "," + j2 + ") ... " + visited[statusKey]); 
    if (visited[statusKey]) { 
     return false; 
    } 
    visited[statusKey] = true; 
    //... rest of isConnectedTo 
} 

후자의 접근 방식 단락 재귀 단순히 이미 알고리즘에 의해 방문한 모든 노드에 대해 "false"를 반환하여.