題目意思：有一個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;
}
