soj1073bfs.cpp

一些ACM题目的解答,主要是soj和poj的

#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;

struct point
{
    int x;
    int y;
    int count;
    point(int a,int b,int c)
    {
        x=a;
        y=b;
        count=c;
    }
};

bool isfit(int a,int b)
{
    if(a>=0&&a<=7&&b>=0&&b<=7)
        return true;
    return false;
}

int main(void)
{
    char a[10],b[10];
    bool icon[8][8];
    while(scanf("%s%s",a,b)==2)
    {
        queue<point> my;
        memset(icon,false,sizeof(icon));
        point end(b[0]-'a',b[1]-'1',0);
        my.push(point(a[0]-'a',a[1]-'1',0));
        while(!my.empty())
        {
            point t = my.front();
            my.pop();
            icon[t.x][t.y]=true;
            if(t.x==end.x&&t.y==end.y)
            {
                printf("To get from %s to %s takes %d knight moves.\n",a,b,t.count);
                break;
            }
            if(isfit(t.x-2,t.y+1)&&!icon[t.x-2][t.y+1])
            {
                my.push(point(t.x-2,t.y+1,t.count+1));
            }
            if(isfit(t.x-2,t.y-1)&&!icon[t.x-2][t.y-1])
            {
                my.push(point(t.x-2,t.y-1,t.count+1));
            }
            if(isfit(t.x+2,t.y+1)&&!icon[t.x+2][t.y+1])
            {
                my.push(point(t.x+2,t.y+1,t.count+1));
            }
            if(isfit(t.x+2,t.y-1)&&!icon[t.x+2][t.y-1])
            {
                my.push(point(t.x+2,t.y-1,t.count+1));
            }
            if(isfit(t.x+1,t.y-2)&&!icon[t.x+1][t.y-2])
            {
                my.push(point(t.x+1,t.y-2,t.count+1));
            }
            if(isfit(t.x+1,t.y+2)&&!icon[t.x+1][t.y+2])
            {
                my.push(point(t.x+1,t.y+2,t.count+1));
            }
            if(isfit(t.x-1,t.y+2)&&!icon[t.x-1][t.y+2])
            {
                my.push(point(t.x-1,t.y+2,t.count+1));
            }
            if(isfit(t.x-1,t.y-2)&&!icon[t.x-1][t.y-2])
            {
                my.push(point(t.x-1,t.y-2,t.count+1));
            }
        }
    }
    return 0;
}