PKU 2243. Knight Moves. [판정:AC]

The Triangle을 풀기 이전에 손코딩으로 풀었던 문제입니다 -_-;

처음에는 시작점에서 n번만에 갈 수 있는 모든 위치를 표시하고

각 거리마다 어떤 규칙이 있는지 파악하려고 했었습니다만,

( 여기에서 거리란, 시작점에서 가로나 세로로만 움직여서 도착점까지 갈 때 필요한 움직임의 수를 의미합니다 )

( 즉 a1에서 c2까지의 거리는 3이고, b4에서 h7까지의 거리는 9라고 간주합니다 )

일정 거리까지만 규칙이 보이고 그 이후에는 규칙이 잘 보이지 않았습니다

그래서 벡터를 사용하여 문제를 풀기로 했습니다

( 자료구조적 벡터 말고 수학적 벡터 -_-; )

가만 보면,

시작점으로부터 거리가 짝수인 위치로는 짝수번만에 이동이 가능하고

시작점으로부터 거리가 홀수인 위치로는 홀수번반에 이동이 가능했습니다

(그림1)

(그림2)

그래서

거리가 짝수인 점들에 대해서 규칙을 찾고

거리가 홀수인 점들에 대해서 규칙을 찾기로 했습니다

그 중, 거리가 짝수인 점들은 가로로 짝수, 세로로 짝수만큼 이동해야 하는 점들과

가로로 홀수, 세로로 홀수만큼 이동해야 하는 점들을 구분했습니다

그래놓고나서 보니

몇가지 벡터의 합에 의해 모든 위치로의 이동을 표현할 수 있게 되었습니다 -_-;

위와 같은 과정을 통해 손코딩을 한 결과가 아래와 같습니다

전 롱코딩이 체질인가봐요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

#include <stdio.h> typedef struct point { char col; int row; } point; typedef struct vector { int x; // difference of column of 2 points int y; // difference of row of 2 points } vector; point p1, p2; vector difference( point a, point b ); int knightmoves( vector v ); void main() { int moves = 0; vector diff; while( scanf("%c%d %c%d", &p1.col, &p1.row, &p2.col, &p2.row) != EOF ) { diff = difference(p1, p2); moves = knightmoves(diff); printf("To get from %c%d to %c%d takes %d knight moves.\n", p1.col, p1.row, p2.col, p2.row, moves); getchar(); } } vector difference( point a, point b ) { vector v; int temp; temp = a.col - b.col; if( temp >= 0 ) v.x = temp; else v.x = -temp; temp = a.row - b.row; if( temp >= 0 ) v.y = temp; else v.y = -temp; if( v.y > v.x ) // if y > x, then swap them { temp = v.y; v.y = v.x; v.x = temp; } return v; } int knightmoves( vector v ) { int c = v.x, r = v.y; int dist = c + r; // rectangular distance int mult = c * r; // rectangular area if( dist % 2 == 0 ) // even distance { if( r % 2 == 0 ) // <even, even> { // special cases if( dist == 0 ) return 0; else if( dist == 2 ) return 2; else if( dist == 4 && mult == 0 ) return 2; else if( dist == 6 && mult != 0 ) return 2; // otherwise if( dist < 8 ) { v.x -= 2; return (2 + knightmoves(v)); } else if( mult % 24 == 0 ) { v.x -= 4; return (2 + knightmoves(v)); } else { v.x -= 4; v.y -= 2; return (2 + knightmoves(v)); } } else // <odd, odd> { // special cases if( mult == 1 ) { if( (p1.col < 'c' && p1.row < 3) || (p1.col > 'f' && p1.row > 6) ) { if( (p2.col < 'c' || p2.col > 'f') && (p2.col - 'a' == p2.row - 1) ) return 4; else return 2; } else if( (p1.col < 'c' && p1.row > 6) || (p1.col > 'f' && p1.row < 3) ) { if( (p2.col < 'c' || p2.col > 'f') && (p2.col - 'a' == 8 - p2.row) ) return 4; else return 2; } else return 2; } else if( mult == 3 ) return 2; else if( mult == 9 ) return 2; // otherwise if( mult == 15 ) { v.x -= 3; v.y -= 3; return (2 + knightmoves(v)); } else if( mult < 25 ) { v.x -= 3; v.y -= 1; return (2 + knightmoves(v)); } else { v.x -= 4; v.y -= 2; return (2 + knightmoves(v)); } } } else // odd distance { // special cases if( dist == 1 ) return 3; else if( mult == 2 || mult == -2 ) return 1; // otherwise if( mult == 0 ) { v.x -= (4 + 2 * (dist > 6)); v.y -= 2; return (2 + 2 * (dist > 6) + knightmoves(v)); } else if( c - r == 1 ) { v.x -= 1; v.y -= 2; return (1 + knightmoves(v)); } else { v.x -= 2; v.y -= 1; return (1 + knightmoves(v)); } } }