{"problem":{"name":"「HGOI-1」Water","description":{"content":"水桶可以描述为一个 $h\\times w$ 的竖直平面，其中 `.` 表示空格，`#` 表示挡板，保证除顶面外所有边界均有 `#`。 $\\text{uuku}$ 给水桶装水的方式很奇特：他希望在装水完成的瞬间水不流动。即对于任意一格存在水的位置，其左右和下方均有水或者挡板。并且如果一格水的上方是空格，则称之为水平面，如果上方是挡板或者水桶外部，则称之为上界面。水形成的四连通块内的所有水平面都要一","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8485"},"statements":[{"statement_type":"Markdown","content":"水桶可以描述为一个 $h\\times w$ 的竖直平面，其中 `.` 表示空格，`#` 表示挡板，保证除顶面外所有边界均有 `#`。\n\n$\\text{uuku}$ 给水桶装水的方式很奇特：他希望在装水完成的瞬间水不流动。即对于任意一格存在水的位置，其左右和下方均有水或者挡板。并且如果一格水的上方是空格，则称之为水平面，如果上方是挡板或者水桶外部，则称之为上界面。水形成的四连通块内的所有水平面都要一样高且所有上界面都应该不高于水平面（该条件即为在真空环境且存在重力时水不流动）。\n\n从装水完成后开始计时，每秒都会进行一次扩展。每次扩展所有水平面都会向上方的空格**扩展一层**，并填充**高度小于等于新扩展层的**所有可达的空格（可以理解为仍满足 $\\text{uuku}$ 的上述要求），这一切可以看作是瞬间完成的。\n\n神奇的水会一直扩展，直到**所有可达的空格**均被水填满后停止扩展，即不存在水平面。\n\n现在 $\\text{uuku}$ 想知道，对于所有符合他要求的装水方案，所有水停止扩展所需时间的**平均值**是多少。\n\n## Input\n\n第一行两个整数 $h$，$w$，表示水桶的高度和宽度。\n\n接下来 $h$ 行，每行 $w$ 个字符，其中 `.` 表示空格，`#` 表示挡板。\n\n## Output\n\n一行一个整数，表示 $\\text{uuku}$ 给水桶装水需要的时间的平均值，由于答案可能很大，所以你只需要给出对 $998244353$ 取模以后的结果。\n\n[samples]\n\n## Background\n\n$\\text{uuku}$ 每天都给他的线段树浇水。但由于线段树是平面的，所以 $\\text{uuku}$ 用一个二维的水桶给它浇水。\n\n## Note\n\n#### 样例 1 解释\n\n装水无需时间。\n\n共有 $9$ 种情况（`*` 表示水）：\n\n$1$：\n\n```\n#...#...#\n#.#...#.#\n#########\n```\n需要 $0\\text{s}$。\n\n$2$：\n\n```\n#...#...#\n#*#...#.#\n#########\n```\n需要 $1\\text{s}$。\n\n$3$：\n\n```\n#...#...#\n#*#***#.#\n#########\n```\n需要 $1\\text{s}$。\n\n$4$：\n\n```\n#...#...#\n#*#***#*#\n#########\n```\n需要 $1\\text{s}$。\n\n$5$：\n\n```\n#...#...#\n#.#***#.#\n#########\n```\n\n需要 $1\\text{s}$。\n\n$6$：\n\n```\n#...#...#\n#.#***#*#\n#########\n```\n\n需要 $1\\text{s}$。\n\n$7$：\n\n```\n#...#...#\n#*#...#*#\n#########\n```\n\n需要 $1\\text{s}$。\n\n$8$：\n\n```\n#...#...#\n#.#...#*#\n#########\n```\n\n需要 $1\\text{s}$。\n\n$9$：\n\n```\n#***#***#\n#*#***#*#\n#########\n```\n\n需要 $0\\text{s}$。\n\n因此期望为 $\\dfrac{7}{9}\\equiv 110916040(\\bmod 998244353)$。\n\n#### 数据范围\n\n本题采用**捆绑测试**，共有 $5$ 个 $\\text{subtask}$，最终分数为所有 $\\text{subtask}$ 分数之和。\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|}\\hline\n\\textbf{Task} & \\textbf{Score} & h,w\\le \\cr\\hline\n1 & 10 &  10 \\cr\\hline\n2 & 20 &  100 \\cr\\hline\n3 & 20 &  500 \\cr\\hline\n4 & 20 &  2000 \\cr\\hline\n5 & 30 &  5000 \\cr\\hline\n\\end{array}\n$$\n\n对于 $100\\%$ 的数据，$1 \\le h,w \\le 5000$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8485","tags":["并查集","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["3 9\n#...#...#\n#.#...#.#\n#########","110916040"],["10 20\n###...###....#######\n##..#.####.##.######\n##.##.####.#.#.#####\n#.#..##..###.#.....#\n#..##.#.#....###.#.#\n####....#.##.#..##.#\n##..###.#.#..#.##..#\n###...#..##.##..##.#\n#.#.#.##.##.##..####\n####################","966268884"],["10 20\n#####.######.####.##\n####.#.#####.###.###\n###.###.####.##.####\n###.###.####.#.#####\n##.#####.###..######\n##.......###.#.#####\n#..#####..##.##.####\n#.#######.##.###.###\n#.#######.##.####.##\n####################","581693010"]],"created_at":"2026-03-03 11:09:25"}}