[chess] 체스 판에서 기사의 최단 경로

여기에 올바른 O (1) 솔루션이 있지만, 기사가 체스 기사처럼 움직이며 무한 체스 판에서 움직이는 경우 :

https://jsfiddle.net/graemian/5qgvr1ba/11/

이것을 찾는 열쇠는 보드를 그릴 때 나타나는 패턴을 알아 차리는 것입니다. 아래 다이어그램에서 사각형의 숫자는 해당 사각형에 도달하는 데 필요한 최소 이동 횟수입니다 (폭 우선 검색을 사용하여 찾을 수 있음).

솔루션은 축과 대각선에 대칭이기 때문에 x> = 0 및 y> = x 케이스 만 그렸습니다.

왼쪽 하단 블록은 시작 위치이며 블록의 숫자는 해당 블록에 도달하기위한 최소 이동 횟수를 나타냅니다.

주목해야 할 3 가지 패턴이 있습니다.

• 증가하는 파란색 세로 그룹 4 개
• “기본”빨간색 대각선 (백 슬래시처럼 왼쪽 상단에서 오른쪽 하단으로 실행)
• “보조”녹색 대각선 (빨간색과 같은 방향)

(두 대각선 세트가 왼쪽 상단에서 오른쪽 하단으로 표시되는지 확인하십시오. 이동 횟수가 일정합니다. 왼쪽 하단 상단 오른쪽 대각선은 훨씬 더 복잡합니다.)

각각에 대한 공식을 유도 할 수 있습니다. 노란색 블록은 특별한 경우입니다. 따라서 솔루션은 다음과 같습니다.

function getMoveCountO1(x, y) {

    var newXY = simplifyBySymmetry(x, y);

    x = newXY.x;
    y = newXY.y;

    var specialMoveCount = getSpecialCaseMoveCount(x ,y);

    if (specialMoveCount !== undefined)
        return specialMoveCount;

    else if (isVerticalCase(x, y))
        return getVerticalCaseMoveCount(x ,y);

    else if (isPrimaryDiagonalCase(x, y))
        return getPrimaryDiagonalCaseMoveCount(x ,y);

    else if (isSecondaryDiagonalCase(x, y))
        return getSecondaryDiagonalCaseMoveCount(x ,y);

}

가장 어려운 것은 수직 그룹입니다.

function isVerticalCase(x, y) {

    return y >= 2 * x;

}

function getVerticalCaseMoveCount(x, y) {

    var normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y);

    var groupIndex = Math.floor( normalizedHeight / 4);

    var groupStartMoveCount = groupIndex * 2 + x;

    return groupStartMoveCount + getIndexInVerticalGroup(x, y);

}

function getIndexInVerticalGroup(x, y) {

    return getNormalizedHeightForVerticalGroupCase(x, y) % 4;

}

function getYOffsetForVerticalGroupCase(x) {

    return x * 2;

}

function getNormalizedHeightForVerticalGroupCase(x, y) {

    return y - getYOffsetForVerticalGroupCase(x);

}

다른 경우는 바이올린을 참조하십시오.

내가 놓친 더 단순하거나 더 우아한 패턴이 있을까요? 그렇다면 나는 그들을보고 싶다. 특히 파란색 세로 케이스에서 대각선 패턴을 발견했지만 아직 살펴 보지 않았습니다. 그럼에도 불구하고이 솔루션은 여전히 ​​O (1) 제약 조건을 충족합니다.

답변

var delta = x-y;
if (y > delta) {
    return delta - 2*Math.floor((delta-y)/3);
} else {
    return delta - 2*Math.floor((delta-y)/4);
}

function distance(x,y){
     // axes symmetry 
     x = Math.abs(x);
     y = Math.abs(y);
     // diagonal symmetry 
     if (x < y) {
        t = x;x = y; y = t;
     }
     // 2 corner cases
     if(x==1 && y == 0){
        return 3;
     }
     if(x==2 && y == 2){
        return 4;
     }

    // main formula
    var delta = x-y;
		if(y>delta){
  		return delta - 2*Math.floor((delta-y)/3);
  	}
  	else{
  		return delta - 2*Math.floor((delta-y)/4);
  	}
}


$body = $("body");
var html = "";
for (var y = 20; y >= 0; y--){
	html += '<tr>';
	for (var x = 0; x <= 20; x++){
  	html += '<td style="width:20px; border: 1px solid #cecece" id="'+x+'_'+y+'">'+distance(x,y)+'</td>';
  }
  html += '</tr>';
}

html = '<table>'+html+'</table>';
$body.append(html);

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

def solve(x,y):
        x = abs(x)
        y = abs(y)
        if y > x:
            temp=y
            y=x
            x=temp
        if (x==2 and y==2):
            return 4
        if (x==1 and y==0):
            return 3

    if(y == 0 or float(y) / float(x) <= 0.5):
        xClass = x % 4
        if (xClass == 0):
            initX = x/2
        elif(xClass == 1):
            initX = 1 + (x/2)
        elif(xClass == 2):
            initX = 1 + (x/2)
        else:
            initX = 1 + ((x+1)/2)

        if (xClass > 1):
            return initX - (y%2)
        else:
            return initX + (y%2)
    else:
        diagonal = x - ((x-y)/2)
        if((x-y)%2 == 0):
            if (diagonal % 3 == 0):
                return (diagonal/3)*2
            if (diagonal % 3 == 1):
                return ((diagonal/3)*2)+2
            else:
                return ((diagonal/3)*2)+2
        else:
            return ((diagonal/3)*2)+1


def test():
    real=[
    [0,3,2,3,2,3,4,5,4,5,6,7,6,7],
    [3,2,1,2,3,4,3,4,5,6,5,6,7,8],
    [2,1,4,3,2,3,4,5,4,5,6,7,6,7],
    [3,2,3,2,3,4,3,4,5,6,5,6,7,8],
    [2,3,2,3,4,3,4,5,4,5,6,7,6,7],
    [3,4,3,4,3,4,5,4,5,6,5,6,7,8],
    [4,3,4,3,4,5,4,5,6,5,6,7,6,7],
    [5,4,5,4,5,4,5,6,5,6,7,6,7,8],
    [4,5,4,5,4,5,6,5,6,7,6,7,8,7],
    [5,6,5,6,5,6,5,6,7,6,7,8,7,8],
    [6,5,6,5,6,5,6,7,6,7,8,7,8,9],
    [7,6,7,6,7,6,7,6,7,8,7,8,9,8]]

    for x in range(12):
        for y in range(12):
            res = solve(x,y)
            if res!= real[x][y]:
                print (x, y), "failed, and returned", res, "rather than", real[x][y]
            else:
               print (x, y), "worked. Cool!"

test()