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

## 第三次AC，纪念！贡献了四次WA

Posted by Matthew_lyns at 2017-04-25 15:50:37 on Problem 1915
```#include <iostream>
using namespace std;

const int MAX_SIZE = 305;
int size;

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

typedef struct
{
int x;
int y;
int step;
}Point;

typedef struct
{
Point visited[90001];
int front;
int rear;
}Queue;

int bfs(Point start, Point end)
{
Queue queue = {{0}, 0, 0};
memset(map, 0, sizeof(map));

queue.visited[0].x = start.x;
queue.visited[0].y = start.y;
queue.visited[0].step = 0;
queue.rear++;
map[start.x][start.y] = 1;

if(start.x == end.x && start.y == end.y) return 0;

while(queue.front < queue.rear)
{
//if(queue.visited[queue.front].x == end.x && queue.visited[queue.front].y == end.y) break;

for(int i = 0; i < 8; i++)
{
int xx = queue.visited[queue.front].x + dir[i][0];
int yy = queue.visited[queue.front].y + dir[i][1];

if(xx >= 0 && xx < size && yy >= 0 && yy < size && map[xx][yy] == 0)
{
queue.visited[queue.rear].x = xx;
queue.visited[queue.rear].y = yy;
queue.visited[queue.rear].step = queue.visited[queue.front].step + 1 ;
queue.rear++;
map[xx][yy] = 1;
if(queue.visited[queue.rear - 1].x == end.x && queue.visited[queue.rear - 1].y == end.y)
{
return queue.visited[queue.rear-1].step;
}
}
}
queue.front++;
}
return 0;
}

int main()
{
Point start, end;
int num;
int result = 0;

freopen("input.txt","r", stdin);
//setbuf(stdout, NULL);
scanf("%d", &num);
while(num--)
{
cin >> size;
if(size < 4) return 0;
cin >> start.x >> start.y;
cin >> end.x >> end.y;

result = bfs(start, end);
cout <<result <<endl;
}
return 0;
}```

Followed by: