ACM 439 Knight Moves

想好久的題目。
後來DS看完array了，
剛好exercise有一題也是knight move，
想說做完這題習題應該就能解這題ACM了，
結果悲劇，根本是不一樣的問題。
習題的題目：隨便給一個點，繞完西洋棋上每個點剛剛好一次。
這題：給兩點，由A點到B點的最短移動次數。

後來想到一種方法，不如從起始點A開始填數字（數字表示移動次數），
把西洋棋盤填滿，這樣就能知道A到B的移動次數。
但是有個問題，不知道能不能依序移動。
（後來看別人的作法，是可以依序移動）
依序移動的意思是，從某個點開始1, 2, 3一直往上填。
所以作法上保守一點，
就從A點開始，填滿所有的1，再從每個1中依序填滿所有的2，以此類推。
每填好一個，就丟到stack中，當所有的1都丟到stack中後，
最先丟進去的1要先拿出來用。依此類推。
有點first in first out的感覺。
應該叫quene不叫stack。

/* ACM 439 Knight Moves
 * mythnc
 * 2011/11/29 16:49:26   
 * run time: 0.024
 */
#include <stdio.h>
#include <string.h>

#define MAXCHAR 3  /* 2 + '\0' */
#define MAXS    8
#define RANGE(X) X >= 0 && X < MAXS

typedef struct point {
    int x; /* row */
    int y; /* col */
} Point;

Point stoc(char *);
void draw(int (*)[], Point);
void filln(int (*)[], Point, Point);

int count;
Point stack[MAXS * MAXS];

int main(void)
{
    char start[MAXCHAR], end[MAXCHAR];
    int square[MAXS][MAXS];
    Point from, to;

    while (scanf("%s %s", start, end) == 2) {
        /* init */
        memset(square, 0, sizeof(square));

        from = stoc(start);
        to = stoc(end);
        draw(square, from);

        printf("To get from %s to %s takes %d knight moves.\n",
                start, end, square[to.x][to.y]);
    }

    return 0;
}

/* stoc: string change to coordinate */
Point stoc(char *s)
{
    Point pt;
    pt.x = s[1] - '1';
    pt.y = s[0] - 'a';

    return pt;
}

/* draw: fill square with numbers */
void draw(int (*s)[MAXS], Point pt)
{
    int i, j;
    Point origin;

    origin.x = pt.x;
    origin.y = pt.y;
    count = 0;
    filln(s, pt, origin);

    for (i = 0; i < count; i++) {
        pt.x = stack[i].x;
        pt.y = stack[i].y;
        filln(s, pt, origin);
    }
}

/* filln: fill blocks to number n */
void filln(int (*s)[MAXS], Point pt, Point o)
{
    int i, x, y, n;
    int movex[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int movey[] = {1, 2, 2, 1, -1, -2, -2, -1};

    n = s[pt.x][pt.y] + 1;
    for (i = 0; i < 8; i++) {
        x = pt.x + movex[i];
        y = pt.y + movey[i];
        if (RANGE(x) && RANGE(y) && s[x][y] == 0
            && (x != o.x || y != o.y)) {
            s[x][y] = n;
            stack[count].x = x;
            stack[count].y = y;
            count++;
        }
    }
}