首先，因为至少有 $M$ 种不同的连通块大小，所以每种颜色的格子数量至少是 $\frac{M(M+1)}{2}$，总和是 $M(M+1)$。所以当 $M\ge N$ 时一定无解。

当 $M < N$ 时，首先考虑构造一个 $M\times(M+1)$ 的子矩形，其中每种颜色大小为 $1,\ldots,M$ 的连通块各出现一次。$M=6,7$ 的例子如下：

.#.#.#
##.#..
...###
###...
..#.##
#.#.#.
#.#.#.

.#.#.#.#
##.#.#..
...#.###
####....
....####
###.#...
..#.#.##

构造的思路是从一个角落开始可以得到大小为 $1,3,5,\ldots$ 且颜色交替的连通块，将其对称且取反后可以得到所有奇数大小的连通块。再对称一次，并且将边界调整一格，就能得到所有偶数大小的连通块。

得到这个 $M\times (M+1)$ 子矩形后，剩下的部分用棋盘染色即可。注意边界上会有连续两个相同颜色的格子，我们将它视为一个整体进行棋盘染色，这样额外的格子的连通块大小不会超过 $2$，且 $M=1$ 时相当于直接棋盘染色。