文档章节

sicily 1781 Knight

Ciel
 Ciel
发布于 2013/01/16 18:58
字数 394
阅读 34
收藏 0

Description

Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another. The possible knight moves are shown in Figure 1.


Figure 1  Possible knight moves on the board

Input

The first line contains an integer T (≤10), indicating the number of test cases.

In every case, the first line contains an integer N (≤500), indicating the size of the chess board (the entire board has size N  × N). The second and third line contain pair of integers (srcR, srcC), and (dstR, dstC), specifying the starting and ending position of the knight on the board (0 ≤ srcR, srcC, dstR, dstC ≤ N – 1).

Output

For every case, output the minimum distance on a single line. If starting point and ending point are equal, distance is 0. If the knight can’t reach the ending point, distance is -1.

Sample Input

2
1
0 0
0 0
10
0 1
8 9

Sample Output

0
6

分析:

简单的BFS查找,注意判断状态是否合法即可。

代码:

// Problem#: 1781
// Submission#: 1896080
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define MAX 500

struct node{
    int x, y, z;
    node(int r, int s, int t){
        x = r;
        y = s;
        z = t;
    }
};

int n, a, b, c, d;
bool visit[MAX][MAX];
int move[8][2] = {{-2, -1}, {-1, -2}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {1, -2}, {2, -1}};

inline bool judge(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < n;
}

int bfs(){
    queue<node> buffer;
    memset(visit, false, sizeof(visit));
    buffer.push(node(a, b, 0));
    visit[a][b] = true;
    while (!buffer.empty()) {
        node tmp = buffer.front();
        if (tmp.x == c && tmp.y == d) 
            return tmp.z;
        buffer.pop();
        for (int i = 0 ; i < 8 ; ++i) {
            int tx = tmp.x + move[i][0];
            int ty = tmp.y + move[i][1];
            int tz = tmp.z + 1;
            if (judge(tx, ty) && !visit[tx][ty]){
                buffer.push(node(tx, ty, tz));
                visit[tx][ty] = true;
            }
        }
    }
    return -1;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        cin >> a >> b >> c >> d;
        cout << bfs() << endl;
    }
    return 0;
}

© 著作权归作者所有

Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
Oracle 11g R2 ADG 搭建

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v$database; 如果为noarchivelog模式,切换到archivelo......

UltraSQL
2018/07/23
0
0
java程序CPU消耗分析之找出最耗CPU线程

java程序CPU消耗过高一般有两种情况: 1、us过高,应用占用CPU资源过高,需找出具体占用CPU的线程所执行的代码,分析定位问题原因。 分析步骤如下: (1) 使用top命令找出占用cpu最高的JAVA进...

天天顺利
2015/09/24
788
0
poj 2488 A Knight's Journey

dfs 注意字典序输出 1 12 34 3 Sample Output Scenario #1:A1 Scenario #2:impossible Scenario #3:A1B3C1A2B4C2A3B1C3A4B2C4 Source [Submit] [Go Back] [Status] [Discuss] /*============......

locusxt
2013/12/19
136
0
acm题目及我的程序(2)——Knight Moves (骑士跳跃)

acm题目,来源 http://acm.zju.edu.cn/show_problem.php?pid=1091 problem statement A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find th......

晨曦之光
2012/03/09
1K
0
(webservice+cxf+mybatis+mysql+springmvc) webservice + cxf 能够跑起来的cxf ,来这里,,

webservice jar 下载: http://download.csdn.net/download/knightblackbob/9186507 webservice server 下载:http://download.csdn.net/download/knightblackbob/9186521 webservice clien......

curiousby
2015/10/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mybatis Plus删除

/** @author beth @data 2019-10-17 00:30 */ @RunWith(SpringRunner.class) @SpringBootTest public class DeleteTest { @Autowired private UserInfoMapper userInfoMapper; /** 根据id删除......

一个yuanbeth
今天
4
0
总结

一、设计模式 简单工厂:一个简单而且比较杂的工厂,可以创建任何对象给你 复杂工厂:先创建一种基础类型的工厂接口,然后各自集成实现这个接口,但是每个工厂都是这个基础类的扩展分类,spr...

BobwithB
今天
5
0
java内存模型

前言 Java作为一种面向对象的,跨平台语言,其对象、内存等一直是比较难的知识点。而且很多概念的名称看起来又那么相似,很多人会傻傻分不清楚。比如本文我们要讨论的JVM内存结构、Java内存模...

ls_cherish
今天
4
0
友元函数强制转换

友元函数强制转换 p522

天王盖地虎626
昨天
5
0
js中实现页面跳转(返回前一页、后一页)

本文转载于:专业的前端网站➸js中实现页面跳转(返回前一页、后一页) 一:JS 重载页面,本地刷新,返回上一页 复制代码代码如下: <a href="javascript:history.go(-1)">返回上一页</a> <a h...

前端老手
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部