Discussion #835 - Problem #404

矩阵外视为空格。

那么首先，第一三行不能有连续的两个空格，否则无解。从而第一三行的空格随时可以填上。
这样，考虑将第二行划分为空格的极长连续段，不难发现连续段之间是独立的。

对每个连续段 DP，从左往右，记录 $f(i,j), g(i,j)$ 表示第二行第 $i$ 列的格子在前 $i$ 列中第 $j$ 个被通过上下/左右填上的方案数。
为了避免重复，钦定四个方向都有棋子的选择其中一种。
转移不太难编，但是需要比较细致。