bfs.cpp

#include <iostream>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int msize = 500;
int maze[msize][msize];

int mov[][2] = {
  {-1,  1},
  {-1, -1},
  { 1,  1},
  { 1,  -1},
};
struct Node {
  pair<int, int> pos;
  int cost;
  Node(pair<int, int> p, int c)
      :pos(p), cost(c)
  { }
};

int sz;
const int kmoves = sizeof(mov) / sizeof(mov[0]);
bool valid(int x, int y) {
  return x >= 0 && x < sz &&
      y >= 0 && y < sz &&
      !maze[x][y];
}

int bfs(pair<int, int> src,
        pair<int, int> dst) {
  queue<Node> que;
  que.push(Node(src, 0));
  while (!que.empty()) {
    Node tmp = que.front();
    que.pop();
    if (tmp.pos == dst)
      return tmp.cost;
    int tx = tmp.pos.first;
    int ty = tmp.pos.second;
    for (int i = 0; i < kmoves; ++i) {
      int nx = tx + mov[i][0];
      int ny = ty + mov[i][1];
      if (valid(nx, ny)) {
        maze[nx][ny] = 1;
        que.push(Node(make_pair(nx, ny), tmp.cost + 1));
      }
    }
  }
  return -1;
}

int main() {
  int n;
  int srcx, srcy;
  int dstx, dsty;

  while (scanf("%d", &n) != EOF) {
    while (n--) {
      scanf("%d%d%d%d%d", &sz, 
            &srcx, &srcy,
            &dstx, &dsty);
      memset(maze, 0, sizeof(maze));
      printf("%d\n", bfs(make_pair(srcx, srcy),
                         make_pair(dstx, dsty)));
    }
  }
}