uva 439 - Knight Moves

点击打开链接

题目意思:有一个8x8的棋盘,初始给定两个位置,求出从第一个位置到第二个位置的最短路

解题思路:对于这一类的求最短路我们一般用广搜来做,开个结构体存储坐标,然后用队列存储这个这个结构体的对象,开始把第一个点放入队列,接下来进行BFS,注意这一题最大的mark标记数组开到750左右,我因为开了1010的数组TLE到蛋疼啊,不懂是不是因为数据实在很多然后每一次都调用memset还有其它的耗时大.

代码:

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 10;//注意数组最大开到750,800以上超时
//存储坐标
struct point{
    int x;
    int y;
};
point p[MAXN];
int mark[MAXN][MAXN];//标记是否走过,我们这里开始为0,每向外广搜一圈就加1 这样最后输出的mark[x2][y2]即为最小步数
int x[8] = {-2,-1,1,2,2,1,-1,-2};//方向数组
int y[8] = {1,2,2,1,-1,-2,-2,-1};
queue<point>q;//队列
int sum , Index;
int x1 , x2 ,y1 , y2;//两个点的坐标
//广搜
void Bfs(){
    while(!q.empty()){
        //把满足条件的插入队列
        for(int k = 0 ; k < 8 ; k++){
            if(x1 + x[k]< 1 || x1+x[k] > 8 || y1+y[k] <1 || y1+y[k] > 8)
                continue;
            if(mark[x1+x[k]][y1+y[k]] >= 1 || (x1+x[k] == p[1].x && y1+y[k] == p[1].y))
                continue;
            mark[x1+x[k]][y1+y[k]] = mark[x1][y1] + 1;
            point temppoint;
            temppoint.x = x1 + x[k];
            temppoint.y = y1 + y[k];
            q.push(temppoint);
            if(temppoint.x == p[0].x && temppoint.y == p[0].y)
                return;
        }
        q.pop();//第一个出队列
        point temp = q.front();//队列第一个存入temp结构体里
        x1 = temp.x; y1 = temp.y;//从新赋值
    }
}

int main(){
    char c1 , c2 ,c3 , c4 , space;
    while(scanf("%c%c%c%c%c%*c" ,&c1 , &c2 , &space , &c3 , &c4)!=EOF){//读入字符注意空格读入还有消去换行
        x1 = c1 - 'a' + 1;
        y1 = c2 - '1' + 1;
        x2 = c3 - 'a' + 1;
        y2 = c4 - '1' + 1;
        p[1].x = x1;p[1].y = y1;//第一个点
        p[0].x = x2;p[0].y = y2;//目标点
        memset(mark , 0 , sizeof(mark));//初始化为0
        Index = 1;
        while(!q.empty())//注意队列每次情空
            q.pop();
        q.push(p[Index]);  //第一次把第一个点插入队列
        if(p[0].x == p[1].x && p[0].y == p[1].y)
            sum = 0;//如果是两点相同直接输出0
        else
            Bfs();
        sum = mark[x2][y2];
        printf("To get from %c%c to %c%c takes %d knight moves.\n" , c1 , c2 , c3 , c4 , sum);
    }
    return 0;
}
时间: 2024-09-09 05:33:46

uva 439 - Knight Moves的相关文章

UVa 439:Knight Moves 搜索专题

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=380 题目类型: 搜索 样例输入: e2 e4 a1 b2 b2 c3 a1 h8 a1 h7 h8 a1 b1 c3 f6 f6 样例输出: To get from e2 to e4 takes 2 knight moves. To get fr

POJ 1915 Knight Moves 双向BFS 入门

 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 o

HDOJ/HDU 1372 Knight Moves(经典BFS)

Problem Description A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks tha

POJ题目分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

poj分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

ACM练级

一般要做到50行以内的程序不用调试.100行以内的二分钟内调试成功.acm主要是考算法的 ,主要时间是花在思考算法上,不是花在写程序与debug上.  下面给个计划你练练: 第一阶段: 练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来.  1.最短路(Floyd.Dijstra,BellmanFord)  2.最小生成树(先写个prim,kruscal要用并查集,不好写)  3.大数(

poj 题型分类

主流算法: 1.搜索 //回溯 2.DP(动态规划) 3.贪心 4.图论 //Dijkstra.最小生成树.网络流 5.数论 //解模线性方程 6.计算几何 //凸壳.同等安置矩形的并的面积与周长 7.组合数学 //Polya定理 8.模拟 9.数据结构 //并查集.堆 10.博弈论 1. 排序 1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 1318, 1877, 1928, 1971,

hduoj题目分类

基础题:1000.1001.1004.1005.1008.1012.1013.1014.1017.1019.1021.1028.1029.1032.1037.1040.1048.1056.1058.1061.1070.1076.1089.1090.1091.1092.1093.1094.1095.1096.1097.1098.1106.1108.1157.1163.1164.1170.1194.1196.1197.1201.1202.1205.1219.1234.1235.1236.1248.1

UVa 10422:Knights in FEN

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=110&page=show_problem&problem=1363 题目类型: 隐式图搜索 原题: There are black and white knights on a 5 by 5 chessboard. There are twelve of each color, and there is o