{"problem":{"name":"「OICon-02」Pick Stone","description":{"content":"小 S 有一个 $n\\times m$ 的棋盘。初始每个位置都有一个棋子。每次，小 S 可以取走一个周围（四连通）被取走棋子数不超过 $1$ 的棋子。求小 S 最多能取走多少棋子，并构造一种合法的取棋子方案。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10172"},"statements":[{"statement_type":"Markdown","content":"小 S 有一个 $n\\times m$ 的棋盘。初始每个位置都有一个棋子。每次，小 S 可以取走一个周围（四连通）被取走棋子数不超过 $1$ 的棋子。求小 S 最多能取走多少棋子，并构造一种合法的取棋子方案。\n\n## Input\n\n一行，两个正整数 $n,m$，表示棋盘大小。\n\n## Output\n\n第一行一个正整数，表示最多能取走的棋子数 $ans$。\n\n接下来 $n$ 行，每行 $m$ 个 $-1\\sim ans$ 之间的整数。每个位置的数表示这个位置的棋子是第几个取走的。如果该位置的棋子没被取走，请输出 $-1$。\n\n[samples]\n\n## Note\n\n### 样例解释\n\n对于样例 $1$，取出 $(1,1)$ 时周围有 $0$ 个已取出位置，取出 $(1,2),(2,1)$ 时周围有 $1$ 个已取出位置，故原构造符合要求。\n\n容易证明没有更优答案。\n\n### 数据范围\n\n**本题采用捆绑测试。**\n\n| $\\text{Subtask}$ | 特殊性质 | $\\text{Score}$ |\n|:--:|:--:|:--:|\n| $1$ | $n=1$ | $20$ |\n| $2$ | $n=2$ | $30$ |\n| $3$ | $n=3$ | $50$ |\n\n对于 $100\\%$ 的数据：$\\bm{1\\leq n\\leq3}$，$1\\leq m\\leq10^5$。\n\n如果你答对了第一问最多能取走的棋子数而没有正确地构造，你将获得 $70\\%$ 的分值。一个子任务你的得分是所有测试点得分的最小值。注意，你仍需要按格式输出 $n\\times m$ 个数表示构造方案，我们推荐你全部输出 $-1$。\n\n保证 `checker.cpp` 在符合格式要求的输出下用时不超过 $0.5$ 秒。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10172","tags":["贪心","Special Judge","O2优化","构造"],"sample_group":[["2 2","3\n1 2\n3 -1"],["3 5","12\n2 3 4 5 6\n1 -1 12 -1 7\n8 9 -1 11 10"]],"created_at":"2026-03-03 11:09:25"}}