骑士.c

算法分析ACM题目：骑士问题算法 保证能运行！算法分析课程必备！

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

int m[100];
int change[8][2]={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};


int dfs(int start,int end)
{
	queue<int> Q;
	int i,tt,tmp,tmpi,tmpj;
	Q.push(start);

	while(!Q.empty())
	{
		tmp=Q.front();
		Q.pop();
		for(i=0;i<8;i++)
		{
			tmpi = tmp/8;
			tmpj = tmp%8;
			tmpi += change[i][0];
			tmpj += change[i][1];
			if(tmpi<0 || tmpi>=8 || tmpj<0 || tmpj>=8)
				continue;
			tt = tmpi*8+tmpj;
			if(m[tt]==-3)
				return m[tmp]+1;
			if(m[tt]==-1)
			{
				m[tt] = m[tmp]+1;
//				printf("m[%d]=%d\n",tt,m[tmp]+1);
				Q.push(tt);
			}
		}
	}

	return -1;
}


int main()
{
	int b,start,end,move,
		i,board=0,tmpi,tmpj;
	char ch;

	while(scanf("%d",&b)>0 && b!=-1)
	{
		board++;
		i = 0;
		memset(m,-1,sizeof(m));
		getchar();
		while(ch=getchar())
		{
			i++;
			if(i%3==0)
			{
				m[tmpi*8+tmpj]=-2;//有棋
			}
			else if(i%3==1)
				tmpi = ch-'a';
			else if(i%3==2)
				tmpj = ch-'1';
			if(ch=='\n')
				break;
		}
		for(i=1;i<=6;i++)
		{
			ch = getchar();
			if(i==3)
			{
				start = tmpi*8+tmpj;
				m[start] = 0;
			}
			if(i%3==1)
				tmpi = ch-'a';
			if(i%3==2)
				tmpj = ch-'1';
		}
		end = tmpi*8+tmpj;
		m[end] = -3;
		
		move = dfs(start,end);
		if(move!=-1)
			printf("Board %d:%d moves\n",board,move);
		else
			printf("Board %d:not reachable\n",board);
	}

}