好奇心宝贝

Luogu
IDLGP10270
Time1000ms
Memory512MB
DifficultyP2
给出一个 $n\times m$ 的矩阵,每个位置 $(i,j)$ 都是一个小写字母。 定义一条路径对应的字符串为路径上字符顺次连接所形成的字符串。 请找出两条从 $(1,1)$ 到 $(n,m)$ 的路径,要求只能向下或向右走,最小化两条路径对应字符串的最长公共前缀。 ## Input 第一行两个数 $n,m$。 接下来 $n$ 行,每行 $m$ 个字符,描述整个矩阵。 ## Output 输出为一个数,即最短的最长公共前缀长度。 [samples] ## Background > 道路,由人亲手制造。 > > 酒与面包,靠劳作取得。 > > 幼小的新芽舒展叶片, > > 与成堆魔药中抵抗困意。 > > 多一点,再多一点时间, > > 再看看书的下一页。 ## Note ### 样例一解释 选择的两条路径分别为: - $(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$,输入均为整数和小写字母。
Samples
Input #1
3 3
abe
bcx
exy
Output #1
2
API Response (JSON)
{
  "problem": {
    "name": "好奇心宝贝",
    "description": {
      "content": "给出一个 $n\\times m$ 的矩阵,每个位置 $(i,j)$ 都是一个小写字母。 定义一条路径对应的字符串为路径上字符顺次连接所形成的字符串。 请找出两条从 $(1,1)$ 到 $(n,m)$ 的路径,要求只能向下或向右走,最小化两条路径对应字符串的最长公共前缀。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10270"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给出一个 $n\\times m$ 的矩阵,每个位置 $(i,j)$ 都是一个小写字母。\n\n定义一条路径对应的字符串为路径上字符顺次连接所形成的字符串。\n\n请找出两条从 $(1,1)$ 到 $(n,m)$ 的路径,要求只能向下或向右走,最小化两条路径对应字符串的最长公共前缀。\n\n## Input\n\n第一行两个数 $n,m$。\n\n接下来 $n$ 行,每行 $m$ 个字符,描述整个矩阵。\n\n## Out...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments