题解 UVA439 骑士的移动 Knight Moves

前言

最近板子题刷多了……

题意

一个 \(8\times 8\) 的棋盘，问马从起点到终点的最短步数为多少。

\(\sf Solution\)

要求最短路径嘛，显然 bfs 更优。

读入

这个读入处理有点麻烦……

我们可以把表示行的字符转化为数字，即 ch-'a'+1 。

搜索

将起点入队，每次获取队首元素并相应扩展，记录步数。

搜到的第一条路径就是最短路径，直接输出 step 。

\(\sf Code\)

#include<cstdio>

#include<cstring>

#include<iostream>

#include<queue>

using namespace std;

struct node

{

	int x,y,step;

} o;

queue<node>q;

int dx[8]={-1,1,-1,1,-2,2,-2,2},

	dy[8]={-2,2,2,-2,-1,1,1,-1};//马的八个方向

bool vis[10][10];//标记数组

int sx,sy,ex,ey,xx,yy;

char ch;

string qx,qy;

int main()

{

	while(cin>>qx&&qx[0]!=EOF)

	{

		cin>>qy;

		sx=qx[0]-'a'+1,sy=qx[1]-'0';

		ex=qy[0]-'a'+1,ey=qy[1]-'0';//读入

		memset(vis,false,sizeof(vis));//初始化

		vis[sx][sy]=true;

		q.push((node){sx,sy,0});

		while(!q.empty())

		{

			o=q.front(),q.pop();

			if(o.x==ex&&o.y==ey)//找到路径

			{

				cout<<"To get from "<<qx<<" to "<<qy<<" takes "<<o.step<<" knight moves.\n";

				break;

			}

			for(int i=0;i<8;++i)//扩展

			{

				xx=o.x+dx[i],yy=o.y+dy[i];

				if(xx<=0||yy<=0||xx>8||yy>8)

					continue;

				if(vis[xx][yy])

					continue;//不符合要求的情况都排除

				vis[xx][yy]=true,q.push((node){xx,yy,o.step+1});

			}

		}

		while(!q.empty())

			q.pop();//别忘记清空队列

	}

	return 0;

}

巴特西

题解 UVA439 骑士的移动 Knight Moves

前言

题意

\(\sf Solution\)

读入

搜索

\(\sf Code\)

最新文章

热门文章