POJ-2243-Knight Moves.txt

/**
POJ2243-Knight Moves
2015-10-07 21:37:54
xuchen
**/
#include "stdio.h"
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 10;
struct node{
	int x, y, step;
	int g, h, f;
	
	bool operator < (const node &a)const
	{
		return f > a.f;
	}
};
int dir[8][2] = {{2,1},{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}};
priority_queue<node> onOpenList;
bool visit[N][N];	//onCloseList
int startX, startY, endX, endY;
int ans;

bool isInMap(int x, int y)
{
	if(x<1 || x>8 || y<1 || y>8)
		return false;
	return true;
}

int Heuristic(int x, int y)
{
	return 10*(abs(x-endX)+abs(y-endY));
}

void AStar()
{
	while(!onOpenList.empty())
	{
		node curNode = onOpenList.top();
		onOpenList.pop();
		node newNode;
		visit[curNode.x][curNode.y] = true;
		if(curNode.x==endX && curNode.y==endY)
		{
			ans = curNode.step;
			return;
		}

		int xx, yy; 
		for(int i=0; i<8; i++)
		{
			
			xx = curNode.x+dir[i][0];
			yy = curNode.y+dir[i][1];
			if(isInMap(xx, yy))
			{
				if(!visit[xx][yy])
				{
					newNode.x = xx;
					newNode.y = yy;
					newNode.step = curNode.step+1;
					newNode.g = curNode.g+23;
					newNode.h = Heuristic(xx, yy);
					newNode.f = newNode.g+newNode.f;
					onOpenList.push(newNode);
				}
			}
		}
	}
}
int main()
{
	char inputs[10];
	while(gets(inputs))
	{
		memset(visit, false, sizeof(visit));
		ans = 0;
		while(!onOpenList.empty())	onOpenList.pop();
		startX = inputs[0]-'a'+1;
		startY = inputs[1]-'1'+1;
		endX = inputs[3]-'a'+1;
		endY = inputs[4]-'1'+1;
		node startNode;
		startNode.x = startX;
		startNode.y = startY;
		startNode.step = 0;
		startNode.g = 0;	
		onOpenList.push(startNode);

		AStar();
		printf("To get from %c%c to %c%c takes %d knight moves.\n", inputs[0], inputs[1],
						inputs[3], inputs[4], ans);
	}
	return 0;
}