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

今天自学BFS。。。都不知道在说什么，然后写的程序就过了= =这尼玛太假了

Posted by xmu_ch at 2013-03-10 00:26:14 on Problem 1915
```#include<iostream>
#include<queue>
using namespace std;
#include<memory.h>
#define maxn 1000
int end_x,end_y;
int l;

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

bool vis[maxn][maxn];

int dir[8][2]={{-2,1},{-2,-1},{-1,2},{-1,-2},{1,2},{1,-2},{2,1},{2,-1}};

int bfs(int x,int y)
{
int d;
memset(vis,false,sizeof(vis));
queue<node>q;
node cur,next;
cur.x = x;
cur.y = y;
cur.step = 0;
q.push(cur);
vis[x][y] = true;
while(!q.empty())
{
cur = q.front();
q.pop();
if(x == end_x && y == end_y)
return cur.step;
for(d = 0; d < 8;d++)
{
next.x = cur.x + dir[d][0];
next.y = cur.y + dir[d][1];
if(next.x >= 0 && next.y >= 0 && next.x <= l-1 && next.y <= l-1 && !vis[next.x][next.y])
{
next.step = cur.step + 1;
if(end_x == next.x && end_y == next.y)
return next.step;
vis[next.x][next.y] = true;
q.push(next);
}
}
}
return -1;
}

int main()
{
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
int n;
int step;
int start_x,start_y;
cin >> n;
for(int i = 0; i < n;i++)
{
cin >> l;
cin >> start_x >> start_y;
cin >> end_x >> end_y;
step = bfs(start_x,start_y);
cout << step << endl;
}
return 0;
}```

Followed by:

User ID:
Title:

Content: