Solution Notes: A much simpler way to look at this problem is to simply count all possible self-avoiding walks from (1,1) to (5,5) that cover all the valid squares. That is, we pretend that there is just one cow who wants to move from (1,1) to (5,5), instead of there being two cows moving at the same time. It is easy to see that there is a one-to-one correspondence between paths involving two cows meeting halfway (as in the original problem statement) and paths involving just one cow who starts at (1,1) and ends at (5,5); the midpoint of the one-cow path would correspond to the meeting point in the analogous two-cow solution.

Now that we know we need to count paths from (1,1) to (5,5), we proceed to enumerate and count all such paths with a recursive function. The "count" function below does this by temporarily noting that the current square is blocked (so we don't return there), temporarily incrementing the blocked square count K, and then recursively visiting all neighbors, accumulating the counts we get from each of them.


#include <stdio.h>

int A[5][5];
int K;

int count(int i, int j)
{
  int c;
  if (i<0 || i>4 || j<0 || j>4 || A[i][j]!=0) return 0;
  A[i][j] = 1; K++;
  if (K==25 && i==4 && j==4) 
    c = 1;
  else
    c = count(i-1,j) + count(i+1,j) + count(i,j-1) + count(i,j+1);
  A[i][j] = 0; K--;
  return c;
}

int main(void)
{
  int i,j,k;

  freopen ("grazing.in", "r", stdin);
  freopen ("grazing.out", "w", stdout);

  scanf ("%d", &K);
  for (k=0; k<K; k++) {
    scanf ("%d %d", &i, &j);
    A[i-1][j-1] = 1;
  }
  
  printf ("%d\n", count(0,0));
  return 0;
}