UVA439-水题

题意：一只棋盘上的马,从一个点到另外一个点要走多少步

解法:广搜

#include<stdio.h>

#include<iostream>

#include <strstream>

#include<string>

#include<memory.h>

#include<math.h>

#include<sstream>

using namespace std;

const int MAXR = 8;

const int MAXC = 'h' - 'a' + 1;

struct Node

{

	int r;

	int c;

	int total;

};

const Node dir[] = { { -1, 2 }, { 1, 2 }, { -2, 1 }, { 2, 1 }, { -2, -1 }, { 2,

		-1 }, { -1, -2 }, { 1, -2 } };

struct Queue

{

	Node a[MAXR * MAXC];

	int total;

	int position;

	Queue()

	{

		total = 0;

		position = 0;

	}

	;

	Node offerNode()

	{

		Node node = a[position++];

		return node;

	}

	void pushNode(Node node)

	{

		a[total++] = node;

	}

	bool empty()

	{

		return position == total;

	}

};

int bfs(Queue queue, Node e, int used[][MAXC + 1])

{

	Node t;

	while (!queue.empty())

	{

		t = queue.offerNode();

		if (t.c == e.c && t.r == e.r)

		{

			return t.total;

		}

		int nt = t.total + 1;

		for (int i = 0; i < 8; i++)

		{

			int er = t.r + dir[i].r;

			int ec = t.c + dir[i].c;

			if (er < 1 || ec < 1 || er > MAXR || ec > MAXC || used[er][ec] == 1)

			{

				continue;

			}

			Node node;

			node.c = ec;

			node.r = er;

			node.total = nt;

			queue.pushNode(node);

			used[er][ec] = 1;

		}

	}

	return 0;

}

int main()

{

	//freopen("d:\\1.txt", "r", stdin);

	char sc, sr;

	char ec, er;

	while (cin >> sc >> sr >> ec >> er)

	{

		int total = 0;

		if (sc == ec && sr == er)

		{

			cout << "To get from " << sc << sr << " to " << ec << er

					<< " takes " << total << " knight moves." << endl;

			continue;

		}

		Queue queue;

		Node s, e;

		s.r = sr - '0';

		s.c = sc - 'a' + 1;

		e.r = er - '0';

		e.c = ec - 'a' + 1;

		s.total = 0;

		queue.pushNode(s);

		int used[MAXR + 1][MAXC + 1];

		memset(used, 0, sizeof(used));

		used[s.r][s.c] = 1;

		total = bfs(queue, e, used);

		cout << "To get from " << sc << sr << " to " << ec << er << " takes "

				<< total << " knight moves." << endl;

	}

}