C语言解答

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
main()
{
	int time,times[8][8]={0, 3, 2, 3, 2, 3, 4, 5, 3, 2, 1, 2, 3, 4, 3, 4, 2, 1, 4, 3, 2, 3, 4, 5, 3, 2, 3, 2, 3, 4, 3, 4, 2, 3, 2, 3, 4, 3, 4, 5, 3, 4, 3, 4, 3, 4, 5, 4, 4, 3, 4, 3, 4, 5, 4, 5, 5, 4, 5, 4, 5, 4, 5, 6};
	char x[3],y[3];
	while(scanf("%s%s",&x,&y)!=EOF)
	{
		if((strcmp(x,"a1\0")==0 && strcmp(y,"b2\0")==0)||(strcmp(x,"a8\0")==0 && strcmp(y,"b7\0")==0)||(strcmp(x,"h1\0")==0 && strcmp(y,"g2\0")==0)||(strcmp(x,"h8\0")==0 && strcmp(y,"g7\0")==0)||(strcmp(x,"b2\0")==0 && strcmp(y,"a1\0")==0)||(strcmp(x,"b7\0")==0 && strcmp(y,"a8\0")==0)||(strcmp(x,"g2\0")==0 && strcmp(y,"h1\0")==0)||(strcmp(x,"g7\0")==0 && strcmp(y,"h8\0")==0))
		{
			time=4;
		}
		else
		{
			time=times[abs(x[0]-y[0])][abs(x[1]-y[1])];
		}
		printf("To get from %s to %s takes %d knight moves.\n",x,y,time);
	}
	return 0;
}

C++解答

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

struct K
{
	int x,y,step;
}start,end;

char s[3],e[3];
int f[][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}},v[8][8];

int bfs()
{
	memset(v,0,sizeof(v));
	struct K head,tail;
	queue<struct K> q;
	q.push(start);
	start.step=0;
	v[start.x][start.y]=1;
	while(!q.empty())
	{
		head=q.front();
		q.pop();
		for(int i=0;i<8;i++)
		{
			tail.x=head.x+f[i][0];
			tail.y=head.y+f[i][1];
			tail.step=head.step+1;
			if(!v[tail.x][tail.y]&&tail.x>=0&&tail.x<8&&tail.y>=0&&tail.y<8)
			{
				if(tail.x==end.x&&tail.y==end.y)
					return tail.step;
				v[tail.x][tail.y]=1;
				q.push(tail);
			}
		}
	}
}

int main()
{
	while(scanf("%s%s",s,e)!=EOF)
	{
		start.x=s[1]-'0'-1;
		start.y=s[0]-'a';
		end.x=e[1]-'0'-1;
		end.y=e[0]-'a';
		if(!strcmp(s,e))
			printf("To get from %s to %s takes 0 knight moves.\n",s,e);
		else
			printf("To get from %s to %s takes %d knight moves.\n",s,e,bfs());
	}
	return 0;
}

Java解答

import java.util.LinkedList;
import java.util.Scanner;


public class Main 
{
	static int[][] to = { { -1, -2 }, { -2, -1 }, { -2, 1 }, { -1, 2 },
		{ 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 } };
	
	
	public static void main(String[]args)
	{
		
		Scanner in = new Scanner(System.in);
		while(in.hasNext())
		{
		boolean vis[][] = new boolean[9][9];
		int time = 0;
		String s = in.next();
		String e = in.next();
		int sx = s.charAt(0) - 'a'+1;
		int sy = s.charAt(1) -48;
		int ex = e.charAt(0) - 'a'+1;
		int ey = e.charAt(1) -48;
		
		point p = new point(sy,sx);
	
		vis[sy][sx] = true;
		LinkedList<point> list1 = new LinkedList<point>();
		LinkedList<Integer> list2 = new LinkedList<Integer>();
		
		list1.add(p);
		list2.add(0);
		while(!list1.isEmpty())
		{
			point p1 = list1.poll();
			time = list2.poll();
			
			if(p1.x == ey && p1.y==ex)
				break;
			
			for(int i = 0;i<8;i++)
			{
					int a = p1.x+to[i][0];
					int b = p1.y+to[i][1];
					
					if(a>0 && b>0 && a<9 && b<9 && !vis[a][b])
					{
						point p2 = new point(a,b);
						list1.add(p2);
						list2.add(time+1);
						vis[a][b] = true;
					}
						
			}
		}
		System.out.println("To get from "+s+" to "+e+" takes "+time+" knight moves.");
		}
	}
}

class point 
{
	int x;
	int y;
	point(int a,int b)
	{
		x = a;
		y = b;
	}
}

Python解答

def moves(x,y):
    s=0
    while x>4 or y>4:
        if x>y>0:
            x-=2
            y-=1
        elif y>=x>0:
            x-=1
            y-=2
        elif x==0:
            x+=1
            y-=2
        elif y==0:
            x-=2
            y+=1
        s+=1
    if x<y:
        x,y=y,x
    if (x,y)in((2,2),(4,4)):
        s+=4
    elif (x,y) in ((1,0),(3,0),(4,1),(4,3),(3,2)):
        s+=3
    elif (x,y) in ((4,0),(4,2),(3,3),(3,1),(2,0),(1,1)):
        s+=2
    elif (x,y)==(2,1):
        s+=1
    return s
corner=(['a1','b2'],['a8','b7'],['h1','g2'],['h8','g7'])
try:
    point=raw_input()
    while point!='':
        point=point.split()
        if point in corner or point[1:]+point[:1] in corner:
            s=4
        else:
            s=moves(abs(ord(point[0][0])-ord(point[1][0])),abs(ord(point[0][1])-ord(point[1][1])))
        print("To get from %s to %s takes %d knight moves."%(point[0],point[1],s))
        point=raw_input()
except:
    pass