(Analysis by Nick Wu)

In this problem, we have a grid of squares, where it is generally possible to travel between two adjacent squares - some pairs of adjacent squares are blocked by roads. There are cows in some of the squares, and we want to know how many pairs of cows will not be able to be in the same square if they are permitted to travel as stated above.

Let us consider one cow arbitrarily. We can determine which squares the cow can reach by doing either a BFS or a DFS. After we have done that, we can then determine which cows can't meet up by checking if that cow's square is reachable.

To determine all the pairs of cows, we perform this BFS/DFS for each cow and count the number of cows that are not reachable, taking care not to overcount.

import java.io.*;
import java.util.*;
public class countcross {

static int n, k, r;

public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("countcross.out")));
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
r = Integer.parseInt(st.nextToken());
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
}
}
for(int i = 0; i < r; i++) {
int x1 = Integer.parseInt(st.nextToken()) - 1;
int y1 = Integer.parseInt(st.nextToken()) - 1;
int x2 = Integer.parseInt(st.nextToken()) - 1;
int y2 = Integer.parseInt(st.nextToken()) - 1;
}
State[] points = new State[k];
int ret = 0;
for(int i = 0; i < k; i++) {
int x = Integer.parseInt(st.nextToken()) - 1;
int y = Integer.parseInt(st.nextToken()) - 1;
points[i] = new State(x, y);
boolean[][] reachable = new boolean[n][n];
dfs(reachable, x, y);
for(int j = 0; j < i; j++) {
if(!reachable[points[j].x][points[j].y]) {
ret++;
}
}
}
pw.println(ret);
pw.close();
}

static int[] dx = new int[]{-1,0,1,0};
static int[] dy = new int[]{0,1,0,-1};

public static void dfs(boolean[][] reachable, int x, int y) {
if(x < 0 || x >= reachable.length || y < 0 || y >= reachable[x].length || reachable[x][y]) {
return;
}
reachable[x][y] = true;
for(int k = 0; k < dx.length; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
dfs(reachable, nx, ny);
}
}
}

static class State {
int x, y;

public State(int x, int y) {
super();
this.x = x;
this.y = y;
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
State other = (State) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}

}
}