一类四邻接网格图森林的匹配问题¶

研究进展（2026-10-12）：背景故事中的三次方上界猜想已有一般证明与结论摘要。题目及输入输出要求保持原定义。

预估时间限制：1 秒。内存限制：128 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(11\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。该倍率为题解中应通过的补充程序保留至少两倍实测余量。

背景故事¶

摸鱼太久之后，某位毒瘤出题人决定研究一个问题。这个问题可能早就有人研究过，只是他从来没有听说过。

他给出一个 \(n\times n\) 的四邻接网格图，每个格子要么是道路，要么是障碍。所有道路格及其上下左右的相邻关系构成一片森林，也就是若干棵树的集合；道路格也可能一个都没有。

提问者会依次告诉你 \(m\) 次移动，每次向某个方向走一格。你需要在初始时和每次移动后，统计有多少个起点能完整执行到目前为止的移动。如果从某个起点出发，途中曾走到障碍上或地图外，即使后来回到道路上，这个起点也不再合法。

当 \(m>n\) 时，出题人猜想自己的解法有 \(O(\max(n^3,m))\) 的时间上界，还尝试构造出需要同阶工作量的数据。不过，他的上下界论证都还不够严谨。如果你能给出严格证明，或指出其中的问题，他很希望听到你的想法。

给出一个 \(n\times n\) 网格，每格为道路或障碍。上下左右相邻的道路格之间有边；全部道路格及这些边构成森林，即若干棵树的并，可以没有道路。

依次给出 \(m\) 个移动方向，每次沿指定方向移动一格。起点合法，当且仅当它本身是道路，且从它出发执行到目前为止的全部移动时，每一步都在网格内的道路上。曾经走出网格或到达障碍的起点永久失效，即使之后回到道路也不恢复。

输出初始以及每一步之后合法起点的数量。行从上向下排列，列从左向右排列。方向零、一、二、三依次表示上、下、左、右。

第一行两个整数 \(n,m\) .接下来 \(n\) 行，每行一个长度为 \(n\) 的字符串，一表示道路，零表示障碍。接下来 \(m\) 行，每行一个方向整数 \(d\) .

输出 \(m+1\) 行。第一行是初始合法起点数，随后各行依次对应执行前一到 \(m\) 次移动后的合法起点数。

0
0
0

样例一初始有七个道路格。向右两次后剩两个起点，再向下一步只剩左上角起点；之后三步仍合法。样例二没有道路，答案全为零。样例三没有移动，只输出初始五个道路格的数量。

\(1\le n\le400\) ，\(0\le m\le10^6\) ，\(d\in\{0,1,2,3\}\) .道路的四邻接图保证为森林。

分值比例	额外条件
100%	无额外条件