# include <iostream>
# include <string.h>
# include <queue>
# define maxn 305
using namespace std;

typedef struct node
{
    int x,y,step;
};

int mark[maxn][maxn];
int n;
node s,e;
int dr[][2]={{1,2},{2,1},{2,-1},{1,-2},{-1,2},{-2,1},{-2,-1},{-1,-2}};
int bfs()
{
    queue<node>q;
    node t;
    int i;
    if (s.x==e.x &&s.y==e.y)return 0;
    q.push(s);
    memset(mark,0,sizeof(mark));
    mark[s.x][s.y]=1;
    while (!q.empty())
    {
        s=q.front();
        q.pop();
        for (i=0;i<=7;i++)
        {
            t.x=s.x+dr[i][0];
            t.y=s.y+dr[i][1];
            if (t.x<0 ||t.x>=n ||t.y<0 ||t.y>=n)continue;
            if (mark[t.x][t.y]==1)continue;
            if (t.x==e.x && t.y==e.y)return t.step+1;
            t.step=s.step+1;
            q.push(t);
            mark[t.x][t.y]=1;
        }

    }
    return -1;
}

int main()
{
    int cas,dis;
    cin>>cas;
    while (cas--)
    {
        cin>>s.x>>s.y;
        cin>>e.x>>e.y;
        s.step=0;
        dis=bfs();
        cout<<dis<<endl;
    }
    return 0;
}
STL 的哪里有问题啊，感觉和下面的一模一样啊

# include <iostream>
# include <string.h>
# define maxn 305
using namespace std;

typedef struct node
{
    int x,y,step;
};

int dr[][2]={{1,2},{2,1},{2,-1},{1,-2},{-1,2},{-2,1},{-2,-1},{-1,-2}};
node s,e;
int mark[maxn][maxn],n;
node queue[maxn*maxn];
int bfs()
{
    int front,rear,i;
    node t;
    front=rear=0;
    queue[rear++]=s;
    memset(mark,0,sizeof(mark));
    while (front<rear)
    {
        s=queue[front++];
        if (s.x==e.x && s.y==e.y)return s.step;
        for (i=0;i<=7;i++)
        {
            t.x=s.x+dr[i][0];
            t.y=s.y+dr[i][1];
            if (t.x<0 || t.x>=n || t.y<0 || t.y>=n )continue;
            if (mark[t.x][t.y]==1)continue;
            t.step=s.step+1;
            queue[rear++]=t;
            mark[t.x][t.y]=1;
        }
    }
    return -1;
}
int main()
{
    int cas,dis;
    cin>>cas;
    while (cas--)
    {
        cin>>n;
        cin>>s.x>>s.y;
        cin>>e.x>>e.y;
        s.step=0;
        dis=bfs();
        cout<<dis<<endl;
    }
    return 0;
}

• Re:STL求解 (2451) proverbs 2012-05-03 23:07:21