範例程式碼 uva439

//uva 439
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <queue>

using namespace std;

int mov[8][2] = {{-1,-2}, {-2,-1}, {-2,1}, {-1,2}, {1,2}, {2,1}, {2,-1}, {1,-2}};

class pos{
    public:
    int r, c, cnt;
    pos() {}
    pos(int _r, int _c, int _cnt) : r(_r), c(_c), cnt(_cnt) {}
    bool operator==(const pos p) {
		return r==p.r && c==p.c;
	}
};

bool legal(pos p) {
    return (p.c >= 1 && p.c <= 8 && p.r >= 1 && p.r <= 8);
}



int main() {
	
    char s[5], t[5];
    queue<pos> q;
    pos cur, goal;
    int ans;
	
    while (scanf("%s %s", &s, &t) == 2) {
        goal = pos(t[1] - '0', t[0] - 'a' + 1, 0);
        while (!q.empty())
            q.pop();
        q.push(pos(s[1] - '0', s[0] - 'a' + 1, 0));
        while (1) {
            cur = q.front();
	    q.pop();
            if (cur == goal) {
                ans = cur.cnt;
                break;
            }

            for (int i = 0 ; i < 8 ; i++) {
                pos tmp = pos(cur.r + mov[i][0], cur.c + mov[i][1], cur.cnt + 1);
                if (legal(tmp)) {
                    q.push(tmp);
                }
            }
        }

        printf("To get from %s to %s takes %d knight moves.\n", s, t, ans);
    }

    return 0;
}