题目意思:有一个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