Posted on 2010-12-17 13:02
Onway 閱讀(401)
評論(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;
}