Posted on 2010-12-17 13:02
Onway 阅读(347)
评论(0) 编辑 收藏 引用 所属分类:
伤不起的ACM
/*
pku 1915 Knight Moves
http://poj.org/problem?id=1915
题目类型：广度优先搜索（分支限界法）
题意：国际象棋中，骑士的移动有一定的规则（具体见原题图），\
给定棋盘大小，骑士的起点和终点，求骑士\
到达终点的最少移动次数。
思路：维持一个队列，将骑士每一步可以到达的点入队，并进行枚举，看是否是终点。\
若当前点不是终点，则以该点为起点，将能到达的点入队。
总结：这个题目其实是入门级的\
广度优先搜索，真没什么好说的，注意一下剪枝就可以。队列可以自己写，也可以用\
STL的queue。\
用了一个点类，是为了入队。其实代码中的same函数可以放入类中的，但不太熟悉，
CE一次（我用VS2010是没事的）。写的过程中思维比较混乱，队列也没有维护好，也\
写了很久。对广搜和深搜真的不太熟练。
*/
#include <iostream>
#include <queue>
using namespace std;
class point
{
public:
int x,y;
point(int i,int j):x(i),y(j){}
};
queue<point> vp;
int num,cnt;
int sx,sy,ex,ey;
bool sgn[401][401];
bool same(int ax,int ay,int bx,int by)
{
if(ax==bx&&ay==by) return true;
return false;
}
void clear()
{
while(!vp.empty())
vp.pop();
}
bool valid(int x,int y)
{
if(x>=0&&x<num&&y>=0&y<num&&sgn[x][y]==0)
return true;
return false;
}
void bfs()
{
point tmp(-1,-1);
while(!vp.empty())
{
tmp=vp.front();vp.pop();
if(same(tmp.x,tmp.y,ex,ey))
{
return;
}
if(same(tmp.x,tmp.y,-1,-1))
{
++cnt;vp.push(point(-1,-1));continue;
}
if(sgn[tmp.x][tmp.y]==1) continue;
sgn[tmp.x][tmp.y]=1;
//right;
if(valid(tmp.x-1,tmp.y+2))
vp.push(point(tmp.x-1,tmp.y+2));
if(valid(tmp.x+1,tmp.y+2))
vp.push(point(tmp.x+1,tmp.y+2));
//left
if(valid(tmp.x-1,tmp.y-2))
vp.push(point(tmp.x-1,tmp.y-2));
if(valid(tmp.x+1,tmp.y-2))
vp.push(point(tmp.x+1,tmp.y-2));
//up
if(valid(tmp.x-2,tmp.y-1))
vp.push(point(tmp.x-2,tmp.y-1));
if(valid(tmp.x-2,tmp.y+1))
vp.push(point(tmp.x-2,tmp.y+1));
//down
if(valid(tmp.x+2,tmp.y-1))
vp.push(point(tmp.x+2,tmp.y-1));
if(valid(tmp.x+2,tmp.y+1))
vp.push(point(tmp.x+2,tmp.y+1));
}
}
int main()
{
int cas;
cin>>cas;
while(cas--)
{
cin>>num>>sx>>sy>>ex>>ey;
clear();
memset(sgn,0,sizeof(sgn));
vp.push(point(sx,sy));
vp.push(point(-1,-1));
cnt=0;
bfs();
cout<<cnt<<endl;
}
return 0;
}