局面合法当且仅当：

• 红子初始时能行动；
• 至少一个红子与黑子相邻，或黑子初始不能行动。

显然可以枚举黑子位置 $(x, y)$，并计算其旁边的空格数目，于是在不考虑「红子初始时能行动」的条件下，可以简单容斥出答案。

有了这个条件，那怎么办呢。可能被多算当且仅当，黑子初始不能行动，且两个红子要么均位于同一个大小为 $2$ 的联通块，要么位于两个大小为 $1$ 的联通块。减掉不合法贡献即可。