uva 439 - Knight Moves
题目意思：有一个8x8的棋盘，初始给定两个位置，求出从第一个位置到第二个位置的最短路
解题思路：对于这一类的求最短路我们一般用广搜来做，开个结构体存储坐标，然后用队列存储这个这个结构体的对象，开始把第一个点放入队列，接下来进行BFS，注意这一题最大的mark标记数组开到750左右，我因为开了1010的数组TLE到蛋疼啊，不懂是不是因为数据实在很多然后每一次都调用memset还有其它的耗时大.
代码：
[cpp]
#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(); www.2cto.com
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;
}
