UVa 439 - Knight Moves

// UVa 439 - Knight Moves

#include <iostream>
#include <string>
#include <queue>
#include <string.h>
#include <stdio.h>
using namespace std;

struct pos {
	int x, y;
};

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

int main() {
	string l;
	while (getline(cin, l)) {
		pos ini = { l[0] - 'a', l[1] - '1' };
		pos fin = { l[3] - 'a', l[4] - '1' };
		int T[8][8];
		memset(T, 255, sizeof(T));
		int oo = T[0][0];
		// bfs
		queue<pos> q;
		q.push(ini);
		T[ini.x][ini.y] = 0;
		while (!q.empty() && T[fin.x][fin.y] == oo) {
			pos now = q.front();
			q.pop();
			for (int k = 0; k < 8; k++) {
				pos next = { now.x + move[k][0], now.y + move[k][1] };
				if (next.x >= 0 && next.x < 8 && next.y >= 0 && next.y < 8 && T[next.x][next.y] == oo) {
					q.push(next);
					T[next.x][next.y] = T[now.x][now.y] + 1;
				}
			}
		}
		printf("To get from %c%c to %c%c takes %d knight moves.\n", l[0], l[1], l[3], l[4], T[fin.x][fin.y]);
	}

	return 0;
}