题解

思路

对每个格子维护三项路径统计：到达该格子的路径条数、这些路径已经出现的 YY 相邻对数量之和，以及这些数量的平方和。

做法

把一条已有路径延伸到相邻格子时，若新经过的边两端都是 Y，则每条路径的计数由 $k$ 变为 $k+1$，对应地一次更新总和与平方和；否则三项统计直接继承。分别从上方和左方汇入即可，右下角的平方和就是答案。

复杂度

每条网格边只处理一次，时间复杂度为 $O(HW)$；使用滚动数组后空间复杂度为 $O(W)$。