Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## STL果然很慢，500MS+

Posted by speedcell4 at 2011-07-25 10:35:39 on Problem 1915 and last updated at 2011-07-25 10:36:22
```#include<iostream>
#include<queue>
using namespace std;
int tcase,l,x1,x2,y1,y2;
struct node
{
int x;
int y;
int t;
node(int a,int b,int c)
{
x=a;
y=b;
t=c;
}
};
int go[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}};
bool canGo[301][301]={false};
bool win(int x1,int y1,int x2,int y2)
{
return (x1==x2)&&(y1==y2);
}
bool within(int x,int y,int l)
{
return (x>=0&&y>=0)&&(x<l&&y<l);
}
int bfs(int x1,int y1,int x2,int y2,int l)
{
queue<node> chess;
chess.push(node(x1,y1,0));
canGo[x1][y1]=true;
while(1)
{
for(int i=0;8-i>0;i++)
{
int x=chess.front().x+go[i][0];
int y=chess.front().y+go[i][1];
int t=chess.front().t+1;
if(within(x,y,l))
{
if(win(x,y,x2,y2)) return t;
else if(canGo[x][y]==false)
{
canGo[x][y]=true;
chess.push(node(x,y,t));
}
}
}
chess.pop();
}
}
int main()
{
scanf("%d",&tcase);while(tcase--)
{
memset(canGo,false,sizeof(canGo));
scanf("%d",&l);
scanf("%d %d",&x1,&y1);
scanf("%d %d",&x2,&y2);
if(win(x1,y1,x2,y2)) printf("0\n");
else printf("%d\n",bfs(x1,y1,x2,y2,l));
}
return 0;
}
```

Followed by: