MCPC 2012 - Problem C : Shortest path in a grid

May Allah`s peace , mercy and blessing be upon you

P.S: This is not the original text, I rephrased and summarized the original one because I'm lazy and I couldn't type the whole text. if there is an error it's my mistake.

[C] LCPC:
Chief judge Fegla and Nicole are in a university and need to meet each other to smoke Shesha O_o' !!! the problem is that all the walkways in the campus form a rectangular grid that has some strange properties :
No one can walk elsewhere the cells of the grid.
Any person on a cell can only go the cell on his left, right, front, rear, the walk takes one second.
Person can't get out of the grid's boundaries.
If a tree is planted in a cell, no one can walk on this cell.
Fegla and Nicole are in two cells(not necessarily different and has no tree)  they start looking for each other taking one action each second simultaneously, your job is to find the minimum number of seconds needed to meet.

Input :
T: number of cases.
R C: number of rows, number of columns.
r1 c1 r2 c2: Fegla's coordinates, Nicole's coordinates.
N: number of trees.
N lines : TRi TCi Tree i coordinates.
1<=R,C<=20, 0<=r1,r2<=R, 0<=c1,c2<=C,
0<=N<=R*C-2, 0<=TRi<=R, 0<=TCi<=C

Output:
Single line either the minimum number of seconds or -1 if they can never meet.

Example :
4
1 3
0 0 0 2
0
2 3
0 0 1 0
0
2 3
0 0 1 2
3
0 2
1 0
1 1
2 3
0 0 0 2
1
0 1

--->
1
1
-1
2

Contest Analysis :
Actually I didn't read this problem during the competition, so this solution wasn't tested against judge's inputs and therefore it's not conclusive.
The key word is Breadth-first search, but first you should notice that Fegla and Nicole are symmetric if Fegla can reach Nicole then Nicole can reach Fegla. Also, if one can't, then the other can't too. So we shouldn't care about both of theme moving, we can fix one and move the other. Now we can use Breadth-first search, but in a grid there is a derivation called the Lee algorithm. First we start from Fegla, then mark every possible(none tree) neighbor with 1, then mark all unlabeled and possible neighbors of 1 with 2 etc...
We stop if we reached the target or we can't mark any more points. In fact, that's it, if we didn't reach the target then, they are in different connected components (in problem's sense). Else, we already have the number of steps that Fegla do while Nicole is stopped. Then, if we make Nicole moves too the number will be divided by two (+1 if odd number).

Solution in C++:

#include <iostream>
#include <fstream>
#include <vector>

#define For(i,n) for(int i(0),_n(n);i<_n;++i)

using namespace std;

static const int P     = 0;
static const int EMPTY = -1;
static const int TREE  = -2;

int main(int argc, char const *argv[]) {
 long long T;
 fstream f("lcpc.in");
 f >> T;
 For(t,T) {
  long long R,C,N,r1,c1,r2,c2,r,c;
  vector<vector<int> > grid;
  f >> R;
  f >> C;
  For(i,R) {
   vector<int> row(C);
   For(j,C) row[j] = EMPTY;
   grid.push_back(row);
  }
  f >> r1;
  f >> c1;
  grid[r1][c1] = P;
  f >> r2;
  f >> c2;
  f >> N;
  For(i,N) {
   f >> r;
   f >> c;
   grid[r][c] = TREE;
  }
  int current = 0;
  bool still = true;
  bool found = false;
  while(still && !found) {
   still = false;
   For(i,R) For(j,C) {
    if(grid[i][j] == current) {
     still = true;
     int val = grid[i][j]+1;
     if(j+1<C) if(grid[i][j+1]==EMPTY)
      grid[i][j+1] = val;
     if(j-1>=0) if(grid[i][j-1]==EMPTY)
      grid[i][j-1] = val;
     if(i+1<R) if(grid[i+1][j]==EMPTY)
      grid[i+1][j] = val;
     if(i-1>=0) if(grid[i-1][j]==EMPTY)
      grid[i-1][j] = val;
     if(i==r2 && j==c2) {
      still = false;
      found = true;
     }
    }
   }
   ++current;
  }
  if(!found) cout << -1 << endl;
  else {
   if(grid[r2][c2]%2 == 0) cout << grid[r2][c2]/2 << endl;
   else cout << grid[r2][c2]/2 + 1 << endl;
  }
 }
 f.close();
 return 0;
}