poj 1915 Knight Moves

Knight Moves

Time Limit: 1000MS

Memory Limit: 30000K

Total Submissions: 26061

Accepted: 12287

Description

Background Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?  The Problem Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.  For people not familiar with chess, the possible knight moves are shown in Figure 1. 

Input

The input begins with the number n of scenarios on a single line by itself.  Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, ..., l-1}*{0, ..., l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario.

Output

For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line.

Sample Input

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

Sample Output

5
28
0

Source

TUD Programming Contest 2001, Darmstadt, Germany

注意:1.数据的下标是从0开始的

   2.注意vis数组每次要置0

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #include<cstdlib>
 6 using namespace std;
 7 const int MAXN=1001;
 8 int vis[MAXN][MAXN];
 9 int map[MAXN][MAXN];
10 int n;
11 int bgx,bgy;
12 int edx,edy;
13 int xx[9]={-1,-2,-2,-1,+1,+2,+2,+1};
14 int yy[9]={-2,-1,+1,+2,-2,-1,+1,+2};
15 struct node
16 {
17     int x;
18     int y;
19     int step;
20 };
21 void bfs(int bgx,int bgy)
22 {
23     queue<node>q;
24     node cur;
25     cur.x=bgx;cur.y=bgy;cur.step=0;
26     q.push(cur);
27     vis[cur.x][cur.y]=1;
28     while(q.size()!=0)
29     {
30         cur=q.front();
31         q.pop();
32         if(cur.x==edx&&cur.y==edy)
33         {
34             printf("%d\n",cur.step); 
35             return ;
36         } 
37         for(int i=0;i<8;i++)
38         {
39             node nxt;
40             nxt.x=cur.x+xx[i];
41             nxt.y=cur.y+yy[i];
42             nxt.step=cur.step+1;
43             if(vis[nxt.x][nxt.y]==0&&nxt.x>=0&&nxt.x<n&&nxt.y>=0&&nxt.y<n)
44                 q.push(nxt),vis[nxt.x][nxt.y]=1;
45         }
46     }
47 }
48 int main()
49 {
50     int T;
51     scanf("%d",&T);
52     for(int i=1;i<=T;i++)
53     {
54         memset(vis,0,sizeof(vis));
55         scanf("%d",&n);
56         scanf("%d%d%d%d",&bgx,&bgy,&edx,&edy);
57         bfs(bgx,bgy);
58     }
59     return 0;
60 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据学习笔记

Hadoop基础教程-第9章 HA高可用(9.3 HDFS 高可用运行)(草稿)

第9章 HA高可用 9.3 HDFS 高可用运行 9.3.1 HA节点规划 节点 IP Zookeeper NameNode JournalNode Da...

2785
来自专栏ml

HDUOJ------2492Ping pong

Ping pong Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ...

3357
来自专栏小樱的经验随笔

HDU 2504 又见GCD(最大公约数与最小公倍数变形题)

又见GCD Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

2923
来自专栏ml

HDUOJ ---1423 Greatest Common Increasing Subsequence(LCS)

Greatest Common Increasing Subsequence Time Limit: 2000/1000 MS (Java/Others)   ...

2915
来自专栏数据结构与算法

POJ 2311 Cutting Game(二维SG+Multi-Nim)

Description Urej loves to play various types of dull games. He usually asks oth...

3548
来自专栏ml

hdu---(1054)Strategic Game(最小覆盖边)

Strategic Game Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/3...

2835
来自专栏c#开发者

Developing a Transactional Biztalk adapter

Contents Developing a Transactional BizTalk Adapter Using the Microsoft Base Ada...

32413
来自专栏ml

HDU----(4291)A Short problem(快速矩阵幂)

A Short problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32...

3516
来自专栏ml

HDUOJ-------2493Timer(数学 2008北京现场赛H题)

Timer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

2684
来自专栏ml

HDUOJ-----2399GPA

GPA Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

3574

扫码关注云+社区

领取腾讯云代金券