好奇心宝贝
题目背景
> 道路,由人亲手制造。
>
> 酒与面包,靠劳作取得。
>
> 幼小的新芽舒展叶片,
>
> 与成堆魔药中抵抗困意。
>
> 多一点,再多一点时间,
>
> 再看看书的下一页。
题目描述
给出一个 $n\times m$ 的矩阵,每个位置 $(i,j)$ 都是一个小写字母。
定义一条路径对应的字符串为路径上字符顺次连接所形成的字符串。
请找出两条从 $(1,1)$ 到 $(n,m)$ 的路径,要求只能向下或向右走,最小化两条路径对应字符串的最长公共前缀。
输入输出格式
输入格式
第一行两个数 $n,m$。
接下来 $n$ 行,每行 $m$ 个字符,描述整个矩阵。
输出格式
输出为一个数,即最短的最长公共前缀长度。
输入输出样例
输入样例 #1
3 3
abe
bcx
exy
输出样例 #1
2
说明
### 样例一解释
选择的两条路径分别为:
- $(1,1)\rightarrow (1,2)\rightarrow (1,3)\rightarrow (2,3)\rightarrow (3,3):$ `abexy`。
- $(1,1)\rightarrow (1,2)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3):$ `abcxy`。
它们的最长公共前缀为 $2$。可以证明没有更优的方案。
### 数据范围与约定
对于 $30\%$ 的数据,$1\le n,m \le 5$。
对于 $50\%$ 的数据,$1 \le n,m \le 50$。
对于另外 $20\%$ 的数据,矩阵随机生成且只含字母 `a,b`。
对于 $100\%$ 的数据,$1 \le n,m \le 2\times 10^3$,输入均为整数和小写字母。