1 条题解
-
0
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; }
Pascal :
program oj_1101; const x:array[1..8]of longint=(-1,-1,1,1,-2,-2,2,2); x1:array[1..8]of longint=(-2,2,-2,2,-1,1,-1,1); var min,xx,xx1,yy,yy1,n:longint; a:array[1..8,1..8]of longint; b:array[1..8,1..8]of boolean; q:string; procedure print(n:longint); begin writeln('To get from ',q[1],q[2],' to ',q[4],q[5],' takes ',n,' knight moves.'); end; procedure search(xx,xx1:longint); var i:longint; begin if n<min then if (xx=yy)and(xx1=yy1)then min:=n else begin for i:=1 to 8 do begin if (xx+x[i]>=1)and(xx+x[i]<=8)and(xx1+x1[i]>=1)and(xx1+x1[i]<=8)then if (b[xx+x[i],xx1+x1[i]]=false)then begin b[xx+x[i],xx1+x1[i]]:=true; //a[xx] inc(n); search(xx+x[i],xx1+x1[i]); dec(n); b[xx+x[i],xx1+x1[i]]:=false; end; end; end; end; begin while not eof do begin fillchar(b,sizeof(b),false); min:=maxlongint; readln(q); xx:=ord(q[1])-96; xx1:=ord(q[2])-48; yy:=ord(q[4])-96; yy1:=ord(q[5])-48; b[xx,xx1]:=true; search(xx,xx1); n:=0; print(min); end; end.
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
- 1
信息
- ID
- 643
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者