Any rectangle whose sides are parallel to the grid is uniquely defined by its top-left and bottom-right points. There are $O(n^2)$ choices for the top-left point and $O(n^2)$ choices for the bottom-right, for a total of $O(n^4)$ possible rectangles. Since $n$ is at most 20, this means that an overall $O(n^6)$ algorithm will be fast enough to get full credit. We have $O(n^4)$ rectangles total, so this means an $O(n^2)$ algorithm for checking whether each rectangle is a PCL will be fast enough to pass.

We can implement such an algorithm using a flood-fill. For each rectangle we check, we first confirm that it only contains two different colors; if it does, then we perform a flood-fill starting from each of the $O(n^2)$ unit squares in the rectangle. However, if a square has already been processed as part of another flood fill, then we skip it. A rectangle will be a valid PCL if and only if it contains exactly three distinct components -- since it contains exactly two colors, this means one of them must have two distinct components and the other must have one. Since each individual flood-fill won't intersect any of the other flood-fills that we start, the total runtime is $O(n^2)$ as each unit square is processed exactly once.

We don't know the total number of PCLs yet, though! We still need to check whether there is a larger PCL that contains the rectangle we're currently considering. It's possible to do this with some clever ordering of the PCLs, processing them in order from largest to smallest, but this can be made significantly easier by noting that there aren't very many rectangles that will be PCLs in the first place. The absolute maximum number of rectangles is ${21 \choose 2}^2$, which is around 44,000. However, the actual number of rectangles will likely be significantly less, as any rectangles without exactly three connected components will be discarded. Therefore, we can simply keep track of all existing PCLs, and to check whether a given PCL is invalid, we test whether any PCL that we have recorded completely contains it.

Our final runtime is $O(n^6 + |PCLs|^2)$.

Here is Brian Dean's code:

#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
using namespace std;

int N;
string img[20];

struct PCL { int i1,j1,i2,j2; };
vector<PCL> V;
bool beenthere[20][20];

void visit(int i, int j, int c, int i1, int j1, int i2, int j2)
{
  beenthere[i][j] = true;
  if (i > i1 && img[i-1][j]-'A'==c && !beenthere[i-1][j]) 
    visit(i-1,j,c,i1,j1,i2,j2);
  if (i < i2 && img[i+1][j]-'A'==c && !beenthere[i+1][j]) 
    visit(i+1,j,c,i1,j1,i2,j2);
  if (j > j1 && img[i][j-1]-'A'==c && !beenthere[i][j-1]) 
    visit(i,j-1,c,i1,j1,i2,j2);
  if (j < j2 && img[i][j+1]-'A'==c && !beenthere[i][j+1]) 
    visit(i,j+1,c,i1,j1,i2,j2);
}

bool is_PCL(int i1, int j1, int i2, int j2)
{
  int num_colors = 0;
  int color_count[26] = {0};
  for (int i=i1; i<=i2; i++)
    for (int j=j1; j<=j2; j++)
      beenthere[i][j] = false;
  for (int i=i1; i<=i2; i++)
    for (int j=j1; j<=j2; j++)
      if (!beenthere[i][j]) {
	int c = img[i][j] - 'A';
	if (color_count[c] == 0) num_colors++;
	color_count[c]++;
	visit(i,j,c,i1,j1,i2,j2);
      }
  if (num_colors != 2) return false;
  bool found_one=false, found_many=false;
  for (int i=0; i<26; i++) {
    if (color_count[i] == 1) found_one = true;
    if (color_count[i] > 1) found_many = true;
  }
  return found_one && found_many;
}

// is x in y?
bool PCL_in_PCL(int x, int y)
{
  return V[x].i1 >= V[y].i1 
    && V[x].i2 <= V[y].i2
    && V[x].j1 >= V[y].j1
    && V[x].j2 <= V[y].j2;
}

bool PCL_maximal(int x)
{
  for (int i=0; i<V.size(); i++)
    if (i!=x && PCL_in_PCL(x,i)) return false;
  return true;
}

int main(void)
{
  ifstream fin ("where.in");
  ofstream fout ("where.out");
  fin >> N;
  for (int i=0; i<N; i++)
    fin >> img[i];
  for (int i1=0; i1<N; i1++)
    for (int j1=0; j1<N; j1++)
      for (int i2=i1; i2<N; i2++)
	for (int j2=j1; j2<N; j2++)
	  if (is_PCL(i1,j1,i2,j2)) {
	    PCL p = {i1,j1,i2,j2};
	    V.push_back(p);
	  }
  int answer = 0;
  for (int i=0; i<V.size(); i++)
    if (PCL_maximal(i)) answer++;
  fout << answer << "\n";
  return 0;
}