{"problem":{"name":"[蓝桥杯 2019 国 AC] 估计人数","description":{"content":"给定一个 $N \\times M$ 的方格矩阵，矩阵中每个方格标记 `0` 或者 `1` 代表这个方格是不是有人踩过。 已知一个人可能从任意方格开始，之后每一步只能向右或者向下走一格。走了若干步之后，这个人可以离开矩阵。这个人经过的方格都会被标记为 `1`，包括开始和结束的方格。注意开始和结束的方格不需要一定在矩阵边缘。 请你计算至少有多少人在矩阵上走过。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8694"},"statements":[{"statement_type":"Markdown","content":"给定一个 $N \\times M$ 的方格矩阵，矩阵中每个方格标记 `0` 或者 `1` 代表这个方格是不是有人踩过。\n\n已知一个人可能从任意方格开始，之后每一步只能向右或者向下走一格。走了若干步之后，这个人可以离开矩阵。这个人经过的方格都会被标记为 `1`，包括开始和结束的方格。注意开始和结束的方格不需要一定在矩阵边缘。\n\n请你计算至少有多少人在矩阵上走过。\n\n## Input\n\n输入第一行包含两个整数 $N$、$M$。\n以下 $N$ 行每行包含一个长度为 $M$ 的 01 串，代表方格矩阵。\n\n## Output\n\n输出一个整数代表答案。\n\n[samples]\n\n## Note\n\n对于所有评测用例, $1 \\leq N, M \\leq 20$, 标记为 `1` 的方格不超过 $200$ 个。\n\n蓝桥杯 2019 年国赛 A 组 G 题（C 组 H 题）。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8694","tags":["搜索","2019","蓝桥杯国赛","Dilworth 定理"],"sample_group":[["5 5\n00100\n11111\n00100\n11111\n00100","3"]],"created_at":"2026-03-03 11:09:25"}}