President's Office

Brutally simple, which means it's dangerously easy to overthink.

Observation

A desk is a deputy iff it shares a side with the President's desk. Since every desk color is unique, we do not count touching cells - we count distinct colors.

If the grid is $g$, then the wanted set is

$$S = \{ g[x][y] \mid \exists (i,j): g[i][j]=c, |x-i|+|y-j|=1, g[x][y]\neq '.', g[x][y]\neq c \}.$$

The answer is just $|S|$.

The whole 'each desk is a rectangle' part is basically a red herring here. Cute, but unnecessary.

Key idea

You might think: find the President's rectangle first. Sure, you can. But that's extra paperwork for zero payoff. If another desk touches the President, then some cell of that desk must be orthogonally adjacent to some President cell. So scanning neighbors of all cells with color $c$ already finds everything.

Also, diagonal contact is useless office gossip. Only the 4 directions matter.

Algorithm

1. Read the grid.
2. Keep a seen array or set for colors already counted.
3. For every cell $(i,j)$ such that $g[i][j]=c$:
   • inspect the 4 neighbors;
   • if a neighbor is inside the grid and its color is neither '.' nor $c$, mark that color as seen.
4. Output how many distinct colors were seen.

Because colors are uppercase Latin letters, there are only $26$ possibilities, so a boolean array of size $26$ is enough.

Why it works

We prove that the algorithm counts exactly the President's deputies.

• If the algorithm adds a color $x$, then there exists a President cell and a neighboring cell of color $x$ with Manhattan distance $1$. So desk $x$ shares a side with the President's desk. By definition, $x$ is a deputy.
• If a desk of color $x$ is a deputy, then it shares a side of positive length with the President's desk. That means at least one cell of color $x$ is orthogonally adjacent to a President cell. When the algorithm scans that President cell, it will see $x$ and add it.

So the set collected by the algorithm is exactly the set of deputy colors. Therefore the final count is correct. No black magic, no geometry cosplay.

Complexity

Each cell is processed once, and for each President cell we check only $4$ neighbors. So the time complexity is

$$O(nm),$$

and the extra memory is

$$O(26)=O(1).$$

This is miles within the limits.