hdu 1372(simple BFS)

水深无声 2021-12-11 11:29 201阅读 0赞

[Problem link adress:click here][Problem link adress_click here]

This is a basic BFS problem.But the way of knight's move  is strange,if you don't know the law of the knight's move,you are likely to cann't work the problem out.However,if you can find the regularity of the problem from the given cases's data,you must be very smart!

#include<iostream>
    #include<queue>
    #include<string>
    using namespace std;
    int map[10][10];
    char s1[5],s2[5];
    int visted[10][10];
    int x1,y1;
    int x2,y2;
    int dir[8][2]={1,2,-1,2,1,-2,-1,-2,2,1,2,-1,-2,1,-2,-1};
    struct node
    {
    	int x,y,step;
    };
    void BFS()
    {
    	int x,y;
    	node cur,next;
    	queue<node>q;
    	memset(visted,0,sizeof(visted));
    	cur.x=x1;
    	cur.y=y1;
    	cur.step=0;
    	visted[x1][y1]=1;
    	q.push(cur);
    	while(!q.empty())
    	{
    		cur=q.front();
    		q.pop();
    		if(cur.x==x2&&cur.y==y2)
    		{
    			printf("To get from %s to %s takes %d knight moves.\n",s1,s2,cur.step);
    			return ;
    		}
    		for(int i=0;i<8;i++)
    		{
    			next.x=x=cur.x+dir[i][0];
    			next.y=y=cur.y+dir[i][1];
    		    next.step=cur.step+1;
    			if(x>=0&&x<8&&y>=0&&y<8)
    			{
    				visted[x][y]=1;
    				q.push(next);
    			}
    
    		}
    	}
    }
    
    
    int main()
    {
    	
    	while(scanf("%s%s",s1,s2)!=EOF)
    	{
    		x1=s1[0]-'a';
    		y1=s1[1]-'1';
    		x2=s2[0]-'a';
    		y2=s2[1]-'1';
    		BFS();
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/heat-man/archive/2012/12/22/2829576.html

[Problem link adress_click here]: http://acm.hdu.edu.cn/showproblem.php?pid=1372