点击打开链接
题目意思:有一个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;
}
分享到:
相关推荐
北大 acm JudgeOnline poj1915 Knight Moves c++源代码
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. ...
moves = { { 2 , 1 }, { 1 , 2 }, { - 1 , 2 }, { - 2 , 1 }, { - 2 , - 1 }, { - 1 , - 2 }, { 1 , - 2 }, { 2 , - 1 }}; Queue q = new LinkedList<> (); q . add( new int []{ 0 , 0 }); Set< String > ...
因子:因子也叫因数,例如3*5=15,那么3和5是15的因子。同时15*1=15,那么1和15也是15的因子。 1,3,5,15 这四个因子是15的所有因子。 完数:如果一个数等于不含它本身的其他因子之和,则称该数为‘完数’。...
该题求解从一个坐标到达另一个坐标的最短步数,移动规则需要按照题目给的方式来移动,即按照国际象棋马的走法一致。
engine-value_moves.c
资源分类:Python库 所属语言:Python 资源全名:peewee-moves-1.6.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
$----------------------- RAPID MOVES ---------------------------------------- $20 Rapid Move in XY (MILL/ROUTER/FLAME/LASER) or XZ (LATHE) only G0 X[AX] Y[AY] $IF CHANGE = 0 G0 G43 H[OFS] Z[AZ] $...
Running-MOVES-2014b-vs-3
knightmoves
微型虚拟机命令: LOAD -- Loads value to R0MOVE_FROM_MEM_TO_REG (Rx),Ry -- Moves the content of (Rx) to RyMOVE_FROM_REG_TO_MEM Rx,(Ry) -- Moves the content of Rx to (Ry)MOVE_FROM_REG_TO_REG Rx,Ry -- ...
TV-MOVES
宝元系统alphacam 后处理 ...$----------------------- RAPID MOVES ---------------------------------------- $20 Rapid Move in XY (MILL/ROUTER/FLAME/LASER) or XZ (LATHE) only G00 X[AX] Y[AY] $IF CHANGE = 0
You have been provided with a third-party library "ChessLib" which calculates the legal moves a knight can make given a position on an 8 by 8 board. The library has been used to create a program which...
# Matlab Wrapper for Fusion Moves (QPBO + alpha-expansion) 作者:Sarun Gulyanon 24.04.2017 --------------------- 描述--------------------- Fusion Moves 是一种基于 QPBO 和 alpha-expansion 的方法,用于...
vbucket-moves.py 是一个分析来自 Couchbase Server 的主事件文件的工具。 主事件文件显示重新平衡事件,可以从。 您需要进行身份验证才能获取文件。 此工具的输出是 vbucket 移动的甘特图,显示移动每个 vbucket 所...
特征Z-Moves Bot具有许多有用而强大的功能。首先,僵尸程序是持久性的,这意味着该僵尸程序具有状态,因为您可以将截止日期和链接添加到数据库中并随时间进行保存。该机器人提供了一些功能:通知事项截止期限链接...
StreetFighterMoves·
Like any good programming book, Eloquent JavaScript begins with fundamentals--variables, control structures, functions, and data structures--then moves on to complex topics like object-oriented ...
Moves considered without alpha-beta pruning: 92 Game Result:-1 Moves considered with alpha-beta pruning: 22 Alpha cuts: 10 Beta cuts: 8 ` 安装 将存储库下载到本地目录 构建java文件javac TicTacToeAI ...