Onway

我是一只菜菜菜菜鸟...
posts - 61, comments - 56, trackbacks - 0, articles - 34

pku 1915 广搜

Posted on 2010-12-17 13:02 Onway 阅读(369) 评论(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;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理