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

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

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

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

## 背景故事

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

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

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

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

## 形式化问题描述

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

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

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

## 输入格式

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

## 输出格式

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

## 样例

### 样例 1

### 输入

```text
4 6
1110
0010
1110
0000
3
3
1
0
2
2
```

### 输出

```text
7
4
2
1
1
1
1
```

### 样例 2

### 输入

```text
2 2
00
00
0
3
```

### 输出

```text
0
0
0
```

### 样例 3

### 输入

```text
3 0
101
010
101
```

### 输出

```text
5
```

## 样例解释

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

## 数据范围与保证

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

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