[TopCoder] ChessMetric (체스 행렬)

당신이 n by n 체스판과 킹나이트라고 불리는 슈퍼피스를 가졌다고 가정해보자. 아래의 'K'로 표시된 킹나이트는 아래의 'X' 또는 'L'로 표시된 공간 중 하나에 도달할 수 있다:
.......
..L.L..
.LXXL.
..XKX..
.LXXL.
..L.L..
.......
즉, 킹나이트는 어떤 방향으로든 한 공간(수직, 수평 또는 대각선)을 이동하거나 'L'자 모양의 이동을 할 수 있다. 'L'자 모양의 동작은 2칸을 수평으로 이동한 후 1칸을 수직으로 이동하거나 2칸을 수직으로 이동한 후 1칸을 수평으로 이동하는 것을 포함한다. 위의 도면에서 'L'자 모양의 이동은 'L'로 표시되는 반면, 한 공간 이동은 'X'로 표시됩니다. 게다가, 킹 나이트는 보드에서 절대 뛰어내리지 않을 수도 있다.

보드의 크기, 킹나이트의 시작 위치 및 킹나이트의 끝 위치를 고려할 때, 당신의 메소드는 정확하게 numMoves 이동에서 시작에서 끝까지 얼마나 많은 가능한 방법이 있는지를 반환할 것이다. 시작과 끝은 각각 2개의 요소를 포함한다. 첫 번째 요소는 (0 기반) 행 위치이고 두 번째 요소는 (0 기반) 열 위치입니다. 행과 열이 각각 아래쪽과 오른쪽으로 증가합니다. 보드 자체에는 0부터 크기-1까지의 행과 열이 있습니다.

참고로, 각각의 이동 순서가 어떤 식으로든 다른 경우 처음부터 끝까지 도달하는 두 가지 방법은 구별된다. 또한 시작에서 끝까지 특정 경로에서 보드의 공백(시작 및 결승 포함)을 반복적으로 사용할 수 있습니다. 우리는 총 경로 수가 2^63-1(a의 상한) 이하임을 보장할 것이다.

Definition

Class:

 

ChessMetric

Method:

 

howMany

Parameters:

 

int, vector <int>, vector <int>, int

Returns:

 

long long

Method signature:

 

long long howMany(int size, vector <int> start, vector <int> end, int numMoves)

(be sure your method is public)

 

Examples

0)

3

{0,0}

{1,0}

1

Returns: 1

Only 1 way to get to an adjacent square in 1 move

 

1)

3

{0,0}

{1,2}

1

Returns: 1

A single L-shaped move is the only way

 

2)

3

{0,0}

{2,2}

1

Returns: 0

Too far for a single move

 

3)

3

{0,0}

{0,0}

2

Returns: 5

Must count all the ways of leaving and then returning to the corner

 

4)

100

{0,0}

{0,99}

50

Returns: 243097320072600

 

---

	L		L
L	X	X	X	L
	X	current	X
L	X	X	X	L
	L		L

 

위의 움직임을 보일 수 있는 체스말이 있다.

 

시작 지점(start)과 도착 지점(end), 그리고 전체 이동횟수(numMoves)가 주어졌을 때 

 

도착지점까지 이동 횟수만큼 이동하는 모든 경로의 경우의 수를 구하는 문제이다. 

 

전체 탐색을 수행하되, 메모화를 이용하여 불필요한 탐색을 없앤다. 

 

#include <vector>
using namespace std;

class ChessMetric{
    public:
    long long howMany(int size, vector <int> start, vector <int> end, int numMoves){
        int dx[] = {1, 1, 1, 0, -1, -1, -1, 0, 2, 1, -1, -2, -2, -1, 1, 2};
        int dy[] = {1, 0, -1, -1, -1, 0, 1, 1, -1, -2, -2, -1, 1, 2, 2, 1};
        long long chessMetric[100][100][50] = {0};
        int sx = start[0];
        int sy = start[1];
        int ex = end[0];
        int ey = end[1];

이동 방향을 나타내는 dx, dy 배열을 선언하고, 체스판을 나타내기 위해 chessMetric를 선언하였다.

 

chessMetric의 세번째 차원은 이동횟수에 대한 차원이다. 

 

마치 시공간처럼 chessMetric[10][10][5] 은 시작점에서 5번 이동했을 때 (10, 10)에 도달하는 경우의 수를 기록한 것이다.

 

나머지 sx, sy, ex, ey는 시작지점의 좌표, 도착지점의 좌표를 나타낸 것이다. 

 

        chessMetric[sy][sx][0] = 1;

 

시작 지점의 0번째 이동의 경우의 수를 1로 지정하였다. 

 

이 1이 for문을 순회하면서 다른 좌표들로 전파될 것이다. 

 

        for(int n=1; n<=numMoves; n++){
            for(int x=0; x<size; x++){
                for(int y=0; y<size; y++){
                    for(int i=0; i<16; i++){
                        int nx = x + dx[i];
                        int ny = y + dy[i];
                        .
                        .

전체 이동횟수, x좌표, y좌표, 이동패턴을 전부 순회하면서 각 시점에 대한 새로운 좌표 nx, ny를 구한다. 

                        if(nx<0 || ny<0 || nx>=size || ny>=size){
                            continue;
                        }
                        chessMetric[ny][nx][n] += chessMetric[y][x][n-1];

새로운 좌표가 체스판을 벗어날 경우 continue한다. 

 

이전 좌표의 이전 시점의 이동의 경우의 수를 새로운 지점의 n번째 이동의 경우의 수에 더해준다. 

 

        return chessMetric[ex][ey][numMoves];

for문을 전부 순회하고 나면 최종 도착지점에 기록된 경우의 수를 반환한다.