ACM (UVa) : 439



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

struct node {
	int row;
	int column;
	int color;
	int value;
} a [8] [8], temp;

queue <node> q;

void reset ()
{
	for ( int i = 0; i < 8; i++ ) {
		for ( int j = 0; j < 8; j++ ) {
			a &#91;i&#93; &#91;j&#93;.row = i; 
			a &#91;i&#93; &#91;j&#93;.column = j; 
			a &#91;i&#93; &#91;j&#93;.color = 0;
			a &#91;i&#93; &#91;j&#93;.value = 99;
		}
	}
}

void set ()
{
	int r;
	int c;

	/* row - 2 / col + 1 */
	r = temp.row - 2;
	c = temp.column + 1;

	if ( r > -1 && c < 8 && a &#91;r&#93; &#91;c&#93;.color == 0 ) { 
		a &#91;r&#93; &#91;c&#93;.value = a &#91;temp.row&#93; &#91;temp.column&#93;.value + 1;
		a &#91;r&#93; &#91;c&#93;.color = 1;
		q.push (a &#91;r&#93; &#91;c&#93;);
	}

	/* row - 1 / col + 2 */
	r = temp.row - 1;
	c = temp.column + 2;

	if ( r> -1 && c < 8 && a &#91;r&#93; &#91;c&#93;.color == 0 ) {
		a &#91;r&#93; &#91;c&#93;.value = a &#91;temp.row&#93; &#91;temp.column&#93;.value + 1;
		a &#91;r&#93; &#91;c&#93;.color = 1;
		q.push (a &#91;r&#93; &#91;c&#93;);
	}

	/* row + 1 / col + 2 */
	r = temp.row + 1;
	c = temp.column + 2;

	if ( r < 8 && c < 8 && a &#91;r&#93; &#91;c&#93;.color == 0 ) {
		a &#91;r&#93; &#91;c&#93;.value = a &#91;temp.row&#93; &#91;temp.column&#93;.value + 1;
		a &#91;r&#93; &#91;c&#93;.color = 1;
		q.push (a &#91;r&#93; &#91;c&#93;);
	}

	/* row + 2 / col + 1 */
	r = temp.row + 2;
	c = temp.column + 1;


	if ( r < 8 && c < 8 && a &#91;r&#93; &#91;c&#93;.color == 0 ) {
		a &#91;r&#93; &#91;c&#93;.value = a &#91;temp.row&#93; &#91;temp.column&#93;.value + 1;
		a &#91;r&#93; &#91;c&#93;.color = 1;
		q.push (a &#91;r&#93; &#91;c&#93;);
	}

	/* row + 2 / col - 1 */
	r = temp.row + 2;
	c = temp.column - 1;

	if ( r < 8 && c > -1 && a [r] [c].color == 0 ) {
		a [r] [c].value = a [temp.row] [temp.column].value + 1;
		a [r] [c].color = 1;
		q.push (a [r] [c]);
	}

	/* row + 1 / col - 2 */
	r = temp.row + 1;
	c = temp.column - 2;

	if ( r < 8 && c > -1 && a [r] [c].color == 0 ) {
		a [r] [c].value = a [temp.row] [temp.column].value + 1;
		a [r] [c].color = 1;
		q.push (a [r] [c]);
	}

	/* row - 1 / col - 2 */
	r = temp.row - 1;
	c = temp.column - 2;

	if ( r > -1 && c > -1 && a [r] [c].color == 0 ) {
		a [r] [c].value = a [temp.row] [temp.column].value + 1;
		a [r] [c].color = 1;
		q.push (a [r] [c]);
	}

	/* row - 2 / col - 1 */
	r = temp.row - 2;
	c = temp.column - 1;

	if ( r > -1 && c > -1 && a [r] [c].color == 0 ) {
		a [r] [c].value = a [temp.row] [temp.column].value + 1;
		a [r] [c].color = 1;
		q.push (a [r] [c]);
	}

}

int main ()
{
	char s1 [5], s2 [5];

	while ( scanf ("%s %s", s1, s2) == 2 ) {

		reset ();
		
		int sourceRow = s1 [1] - '1';
		int sourceCol = s1 [0] - 'a';
		
		int destinationRow = s2 [1] - '1';
		int destinationCol = s2 [0] - 'a';

		a [sourceRow] [sourceCol].value = 0;

		q.push (a [sourceRow] [sourceCol]);

		while ( !q.empty () ) {

			temp = q.front ();
			q.pop ();

			if ( a [temp.row] [temp.column].color != 2 ) {
				a [temp.row] [temp.column].color = 2;
				set ();
			}
		}

		printf ("To get from %s to %s takes %d knight moves.\n", s1, s2, a [destinationRow] [destinationCol].value );  
	}

	return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s