{"problem":{"name":"『STA - R6』inkar-usi","description":{"content":"给一个 $n\\times m$ 的字符矩阵，有些位置有障碍（记为字符 `#`），需要在矩阵上找出一条起始点任意的路径（可以重复经过某个格子），使得字典序最大。 可以证明答案一定是有限的或者是由某个长度有限的字符串 $S$ 不断重复得到的。如果答案是有限的，直接输出之；如果答案是无限的，只需输出它的最短循环节。","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":"LGP10677"},"statements":[{"statement_type":"Markdown","content":"给一个 $n\\times m$ 的字符矩阵，有些位置有障碍（记为字符 `#`），需要在矩阵上找出一条起始点任意的路径（可以重复经过某个格子），使得字典序最大。\n\n可以证明答案一定是有限的或者是由某个长度有限的字符串 $S$ 不断重复得到的。如果答案是有限的，直接输出之；如果答案是无限的，只需输出它的最短循环节。\n\n## Input\n\n第一行两个正整数 $n,m$。\n\n后 $n$ 行，每行一个长度为 $m$ 的字符串，描述矩阵的第 $n$ 行。\n\n## Output\n\n一行一个字符串，表示答案。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/n6w1yuda.png)\n\n（题目背景图片来自 Arcaea 曲绘，如有侵权，请告知出题人。）\n\n## Note\n\n**本题采用捆绑测试。**\n\n数据范围：\n- Subtask 1 (20pts)：字符矩阵中除了障碍就是字母 `A`。\n- Subtask 2 (30pts)：$n,m\\le 3$。\n- Subtask 3 (50pts)：无特殊限制。\n\n对于全部数据，$1\\le n,m\\le 10^3$，所有非障碍字符都是大写字母，矩阵至少有一个非障碍格。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10677","tags":["模拟","贪心","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["3 3\n###\n#A#\n###","A"],["3 4\n####\n#AB#\n####","BA"],["3 4\n####\n#AA#\n####","A"]],"created_at":"2026-03-03 11:09:25"}}