AT_rco_contest_2019_qual_b ファーマーXの収穫計画
题目描述
开始家庭菜园的 X 正在制定蔬菜的养护和收获计划。
X 的庭院由 $N$ 行 $N$ 列的地块组成,在第 $i$ 行 $j$ 列的地块上种有品质为 $A_{i,j}$ 的蔬菜。每个地块的蔬菜只能被收获一次。
X 最多可以执行 $M$ 次以下两种操作中的任意一种。每次操作都需要指定一个尚未被收获的地块。如果指定的地块已经被收获,则什么也不做。
- (1)**养护**:将选中地块上的蔬菜品质增加 $1$。
- (2)**收获**:从选中的地块及其周围的地块收获蔬菜。收获需满足以下条件:
- 设选中地块上的蔬菜品质为 $K$。
- 从选中地块出发,只能沿着上下左右方向,经过“尚未被收获且品质为 $K$ 的蔬菜所在的地块”,连通得到的地块集合记为 $S$。($S$ 包含选中的地块本身。)
- 若 $S$ 中包含的地块数量不少于 $K$,则收获 $S$ 中所有地块上的蔬菜。
- 若 $S$ 中包含的地块数量少于 $K$,则什么也不做。
请制定一个计划,使 X 收获的蔬菜品质总和尽可能大。
每个测试用例的得分以及本题的得分计算方式如下:
- 单个测试用例中,X 收获的蔬菜品质总和即为该用例的得分。
- 总共有 $50$ 个测试用例。所有测试用例得分之和即为本题的得分。
输入格式
输入通过标准输入按以下格式给出。
```
\(\begin{array}{lll}
N ~ M & & \\
A_{ 0,0 } & \ldots & A_{ 0,N-1 } \\
\vdots & \ddots & \vdots \\
A_{ N-1,0 } & \ldots & A_{ N-1,N-1 }
\end{array}\)
```
- $N$ 表示庭院的规模,满足 $N=50$。
- $M$ 表示允许的最大操作次数,满足 $M=2500$。
- $A_{i,j}$ 表示第 $i$ 行 $j$ 列地块上蔬菜的品质,满足 $1\leq A_{i,j}\leq 9$。
输出格式
每行输出一个操作,最多输出 $M$ 行。
```
\(\begin{array}{lll}
\mathit{op}_0 & r_0 & c_0 \\
\mathit{op}_1 & r_1 & c_1 \\
\vdots & & \\
\end{array}\)
```
当 $\mathit{op}_i$ 为养护操作时,输出 `1`,为收获操作时输出 `2`,后跟操作目标地块的行号 $r_i$ 和列号 $c_i$,用空格分隔。
说明/提示
### 关于测试用例的生成
每个测试用例由测试用例生成器随机生成。
测试用例生成器会从 $[1, 9]$ 区间的整数中均匀随机生成 $A_{i,j}$。
测试用例生成器可通过页面底部的链接获取。
### 生成器、测试器与样例输入数据
测试用例生成器、测试器及样例输入数据可通过以下链接获取。
[生成器・测试器・样例输入数据](https://github.com/recruit-communications/rco-contest-2019/tree/master/qual_B/tester)
### 可视化工具
我们提供了一个可视化工具,可以根据输入文件和输出文件计算得分并可视化结果。
- 该可视化工具已在桌面版 [Google Chrome](https://www.google.co.jp/chrome/browser/desktop/index.html) 和 [Mozilla Firefox](https://www.mozilla.org/firefox/new/) 的最新版上通过测试。不能保证在所有浏览器环境下都能正常运行,特别是在 Internet Explorer 上已确认无法运行。
- 可视化工具计算的得分并非本次竞赛的最终得分。请在 AtCoder 上提交解答以获得正式评分。可视化工具计算的得分不保证与竞赛得分一致。
- 使用该可视化工具造成的任何损失,主办方概不负责,请知悉。
可视化工具及其使用方法可通过以下链接获取。
[可视化工具](https://github.com/recruit-communications/rco-contest-2019/tree/master/qual_B/visualizer)
### 样例解释 1
庭院说明与得分如下:

该样例不满足 $N=50,\ M=2500$ 的限制。
0

第一次操作(`2 0 0`)时,从 $(0,0)$ 出发,$S$ 包含的地块为 $(0,0),\ (0,1),\ (0,2),\ (1,1)$ 共 $4$ 个,不满足收获条件。注意与 $(1,1)$ 斜对角相邻的 $(2,0)$ 不属于 $S$。
0

接下来的 4 次操作(`1 1 0` 重复 4 次)将 $(1,0)$ 处蔬菜的品质从 $1$ 依次提升到 $5$。
0
![](data:image/png;base64,%20iVBORw0KGgoAAAANSUhEUgAAAJYAAACWCAYAAAA8AXHiAAAACXBIWXMAAAsTAAALEwEAmpwYAAAgAElEQVR42u19e3Qk5XXn76uq7q5+P9SSWu/RSKNhBjw8El4GmwUMBIxNYsdr7GB2DWQX50ESO5tkNye72SQn62WXNZs1Obbjk/VrbTCsMV4wGBtjm+Fl3oYZRhpppNboNZJa/X5VV33f/tGqmq7u1oxU1epWz9Q9Z86Z0xrV9K3v9917v3vvd38k9ulPM+Hqq4FSCW0pHAfXs8/imUsuQToSARhDuwqlFPl8Hh6PB6xN9RAEAQcPHoQgXH01fJ/6FNpdbvjAB4D+/rbXI51Ow+v1tr0eXNtaqkoplXAm6CHLMiTpzNCDgyWWbIvFssQSC1iWWMCyxAKWJZZYwLLEApYlFrAsscQCliUWsCyxgGWJJRawLNnhIph9QDabRSKRMP1FRFFEKBQCIaQlL6JYLGJ5eRkcZ26v8TyPSCTSsgXNZrOIx+Om3iNjDA6HA52dna0DViaTwfLysukX4vf7EQwGWwYsVQ+zwLLb7S0FVjKZxPLysun36PF4WgusUqlkejEAtAxQquTzefA8b/p7NOJdmJFCoQCe5009gzFm/j2Y+WVKKUoN6IPaCd2S+Xy+Ic9ptS7FYrH9YyzGmA5YgiDA7/cbQrsoii21WoVCQfv/OY4z7JbNWgszoigKKKU6LxAOhw2B3eFw7BxgiaKI3t7elrsDIyLLsva9eZ5Hfxu2OZdKJQ1EjDFtPdou3VANLLvd3vJYqRFu0GazteURvxJYAOB0Olv2XUwBS5Iknem12WxtCaxCoaDbLC6Xq+2BxRhrX2BVxiWEkLbd6ZV6tHqnNxJYrdwgDQWW3W5vywXJ5/OaHq3e6WbjxMq0RyvXgzO7IJUnkHYFVvURXRTFttOBUgpJknZMWHLWu0JKqS5ObNcDSPVBqtXAMpVukCRJy9vwPA+O46AoCgqFAhKJBLLZrKYsx3FwOBzwer3w+/0QBGFHpCXqHdEB1OghyzIopeB5HqIowuPxwOfzwWaz7Qg96p3Q1fXI5/NIJpM166HqsR3rITTCWqlFy7W1NSwvLyOXy4EQov1R/02xWEQymcT8/Dx8Ph/C4TB8Pt+OO0nFYjGsrKxorr7SKsuyjGKxiEQiAUIIfD4fOjo64Pf7dwSw1O8qCAJisRhWV1d1elSvRyKR2Jb1MAWsyvgqk8kgnU6DMVY3+1y5OEB5RkEmk0EoFGppMrISWBzHYW1tDZRSMMbq7uCN9Ojo6EBfX19L9VAtKgDE43HNxW9Fj0AggMHBwdYBq/IkpcYquuCN43S7gzEGSqnudxhjWF1dhSRJGB4ebklMUJ1UVBRlQz1UPatLJIwxLC8vQ1GUhixKI1Imp1qPU+mxtrYGAOjv7zflGhtisSq/rNPpRCAQgNPp1Px8ediFpPVuybKs2zHpdBoLCwst2fH1iuiqaw8Gg5oehBBQSlEsFuvqwXEcYrEYCCEYGBhoScqk3nqIoohAIAC3262d2iv1iMfjUBRFtx6xWAyCIJgqBwmN2iEA0NnZiUgkAkHQP9bhcMDtdiMYDKKzsxMzMzM1Fm9lZUV7Ac08EVYDi1KqubV6Lt3lciEQCKCrqwvRaBS5XE5nFeLxOLxeLwKBQMstVldXFyKRyIZ6BINBdHd3Y3p6GtlsVrNQHMdheXkZbrfbcOzIGV0QQojOvKqxUjWoqsXhcGDv3r11h4vNz883facriqLTo7u7G4ODg6fsUlBzdqOjozXZbcYYYrFYjSvabpEkSdODEIJIJLLh5qgUm82GsbGxGgARQrCwsNBci6Wae7VNg1KKUCi0pWfs2rULExMTmsUghCCbzaJQKDQtQUkIQU9Pj5ZKALAlS0MIwfDwMN59910dkDKZDGRZbmrCeHBwUNc2s9XTXX9/PyYmJnQxpizLyGQy8Hg8zQOWWZclCAKCwaCurZkQgng8jp6enqYBy2w9TRAEdHV1YWFhQXMllFLtxNssMbsedrsdgUAAq6urmvWmlCKXyxkCVksze263W3fyIIToYpZ2kWoAtasewWCwJjyRJMlQo2BLgeVwOGoOAKU2HPlYr07ajnq4XK4aEFWnX9oCWNW5lcqEXbtJO3bN1tsgjXr/LX0biqLU7JBW9oybkWo9Tnc6bhc9jG6YLWtPKUUqldJl1b1eryFAVGe9K4vAzQB1Op2uafAzcpKrLgA3U49SqaSL5xhjcLvdhjpNqnOLajrCiBUTjCzI8ePHNUBQSrFr1y5DCcFCoaA7pjPGDJ1AjAJrZmZGtyN7e3sRDoe3/KxMJgNKqfYsdXGbIZIkYW5uTouFGGPo6elBV1fXlp9VaTBU12j0ts6W7RzHcRAEQav/AeWCpxHLl0wma3x8szLWqmVS9WCMIZvNGjoBLS0t6RZEFMWm5bCq9QBgaOSBmtit1IPjOMMbxBCwKlt3CSFIJpNbvvCZSCSQyWR0QDNiLcyIz+fTASmVSm35wufKykpNOcXn8zUtVrTZbDVuT60DbkVWV1d1rc1qz7zRDbJlYBFC4PV6a0zmzMzMpo+muVwOx48f1z1DTTQ2Uzo7O3WuWHWPm7Va2WwWJ06c0LlTM5ddjUpHR4dOD0op5ufnN61HoVDA0tKS7t9TSk21MxkK+YPBYM0ukSQJk5OTNXFTdVyTSCQwOTlZ87NwONz0nnm3263jrSGEoFgs4siRI8jn8xvqoR5gpqendZuJMQa/39/UQroKLIfDoQNGLpfD+Pj4KddDDUfGx8drYt3e3l5T62HoTMxxHAYHB2sAks/nMT4+Dp/PB6fTqYFP7SLIZDJad2m1yW22tVL16OnpwbFjx3SLUiwWcfToUXg8Hrjdbi11oF5YyOVyyGQyOktFKYXH42lJywxQrr1OTU1pACGEoFAoYHx8HF6vt0aPU62Hx+NBd3e3qe8jmNntIyMjukVRv2AqlapJSVRahUolHA4HRkZGWpa/8ng8GB4extTUlK4niTGGdDqNdDqt+6xefkfdHLt27WpZgtflcmFwcBAzMzM171rVo7rxsjohyhiD3W7H0NCQaT0EmMgYezwejJ1zDqLRKIrFIihjqPw67KSG+hMIAJ7j4PV6MTQ4CGLe9Jj6da/Xi/379yMajSKfz9eNTTaKVziOg8fjwdDQUEOy72ae4ff7NT0KhcKG37keaNTYeWhoqCE6CK5nn1UzbYYeIhKCvYwhkUggnU7XTDuptzACz8Pn98OrtnaYGf3DccBTTyF54ADkQMDwswghCIVCSCaTSKZSYOs9Z9WzotReeEopeEEo3zoKBJBIJGB2gFEul8PPf/wjOEWD1+jYyXcej8eRTqdP5rfWXzNb3+dEXR/GYLPZ4PP54Pf78doLvyivlcHdLggCXnjuIMhTX/wiu+GWWxrC96eBhzGUZLmcWV9PHNrsds3HkzpWzIwkV1Yg7tsHvkE3mCtzQqVSSavwq1fY1DxeI2trADAxdQzn3vl5OC+41jRTLAFAGQMYA0cIAg6CDpGDKAC5ErCSp0hJJ+MxQggaNdnLSQsQ0pFIw5hJK1+xff1PM4T6fOCdzm2pz9nt9qad8jiOB2w+FL19DacgXgSwQBmwflmaOAnINkwSYAAcRILQzhzKZ6aw6gi1YZteb1zZtupgjeO2ZHusr/UKLLGAZYkFLEssYFliiQUsSyxgWWIByxJLLGBZYgHLkrNVBOsVnPmidjacLOOQ9UYAgFjAsmTLYJIpwBgGwi4Mh5wIOgVwhKAgU6xlSxhfySKRlgCeA8eTnQWsdDqNWCxmmk5NbU9uVQdmoVDA/Py86WY9QRBa1p6sCl1v6bnn/YO4+7I+dHnssPMcBI6AkPLPZYWhqDC8OpfC3z87g4MTa+Ds/M4BVi6Xawh1L9AYAkajkslkkEwmG8Kw2mp5764AHr7tPPR6T3HZdL2X8Ma9HbhxbwceeusEPvv4USykiuAasAYNYVht10Ee1Rar3pCSrUor3wVVKP74/YP4wofGtvy7Hz+/Gxf1eXHnI0fw3NE1cDZzG2xbGFYrbxdv9s9OAFYj9GiVLpQxfOKiHnz+xtEN/81bixn8dCqOw8v1L7PuCbvw0O+ci/f0e0FZCy1W9TAMnufhcrkM7Vqjv9dIYFXe0vF4PMaGYbRoykzE68Df3bAbDkFvK2YTBfztMzP46kvzgELLx0AGQODxu5f14j9eO4x+/0mX2eN14D9fvxu/8+1DKCp0ZwDL5XJh9+7d7XeCWtdDja8EQWgrPWiJ4k/eN4DdIX2v8ffeWcEdDx9GMiOB2HiQiit2DMA/HTyOx99dxVd/ex9u2tuh/ey3zu3EJYM+/PxY3HC81VCGVZvNtiPc2lalel5DO7GYUQYEPDb82VX6a1uvzadx9/eOIFVQwNn4mnwVAcDZeSylJNz58Lt4Z0nvHu//0BggGbdYpoCl0mxUAqvdqXvbjq9QpviDKwaqPmJ44IU5rGSk016GIgRYShfxv19d0F1/uKDXg719HlCDwZZpvkKLYbXlfhwfe49+PEEiL+OJI6sg3OY2OQHBTybXkCzIus//+MpBQKbNB1Y1UdOZwrDaLkSYDIDf60C3R//ep+N5LK8VNl2uIQR4ZymLbEk/Lej6PSHDNR/LYtWJsdqGbJwB3V4bbFXlmLeXMlsGBC3IKMp6t+cTBQyGXYYuim07J/ROyVNt+EKrGFY32hw7VQ9R4GtObqmCsRHamaLeFToEDsMhp6Grp6bSDZVHdJVhFShP64vH4zWDKQRBgMfj0Vi1doLUI8LUYpV1PaqnFfI8D6/Xi1Ao1HK3KVMKVmVT3DZjNT9XVa3QzhN0eezrTpc0B1iV8ZU6jiiVSiEajWp0a/XIAXK5HJaWluDz+dDb29tyt1M9uVkURaRSKczOzmrlqnp65PN5TY/+/v7WAIwA8bwMuerktrtD3PJFZ7vLBldVGUfgCcIuY+EN1whgqRQf09PT2vTgjdIOhBDwPI9MJoPJyUksLi7uGGARQpBKpTA1NVXDCnYqPcbHx1uiBwGwmCwiX9Kf3PZ3u2F3bt5mMAac2+2psVgcITWZ/KYAq/KlVw9GVWOXSoaw6oVRmUmPHTu2YyyWSs+2FT0AYHl5GdPT0y3JY/1sSt9d4hcFXDsaLE+b2eTp8ro9IfhFoQa4RoFlirq3nvA8D5/Ph1AoBKfTCZ7nNXbVeDyObDZbszgqw6oZRk8zwNpID7/fj2AwqNUxVVcei8WQy+Vq9Egmkzh+/Hhz+7EEDg+8OIfbfy1yMlay8bj7sn78YjqBXImeMjqijGE45MTvXd5X998ZTXcbBlaxWKxxE8FgED09PTUnK7vdDrvdjmAwiFwuh8XFRaRSKV3v08rKStMHw27EsBoOhxGJRDbUIxAIaHpUjhQnhGBtbU0bYtYM4TiCXx6L45nJOK4dDWqff3h/GH//GyP4iyenkM+VAIEDt54wZQCYwgDKcP3+MO69aRRDQbGuJSs0M0FKKdXII1U3EQ6HMTg4eNpcllqoDoVCNZN6m82wyhgrj7is0KO/vx8DAwOb1sPtdtekIZrNsErsPO5+9Agykj7NcM8VAzj0ucvw2WuHMRQUQUsKaEEGYww37OvAk//mQnz/9gM4v+ckG4isMJ01KxoElmEizD179mhxh6IoW9qhKkNrNpvVMaxmMpmmMqzyPI/h4WEoiqKdZLdCuUIIwcjICN5++20duNLpdFMZVgmAqdU8Pvf4JP7XLXtg50/ai+GgiPs+OIr7Pjh62uf86ROT+O8V/45S1IB1Wy2WyrHicrng8XgMmX2O42oIJDmOa1ib86aP2XY7nE4nvF6vIR4flX+5eoB/pYtsCrgI8JUX53DPY0cNgeG+X8ziyfGY7jNJoVhKS4YirZbeK3S5XGcEw2ogEKhh6miFHhxP8JWX53Hh/b/EE0dim/qdeF7Gx771Nv70/x3Fhb2eKmAxLKWLhgL4ll7/stvtZwTDKsdxsNlsupRL5d+bbbmm1vK4+cuv48CQH3dd3IOrdgfR4bZppR9JoXhtLo1vvr6I7/9qGeAIoFBcNqj3PEWZYiZeMHQ0FFq9INXAasdGQUJIze2eVupBABAHj18tpHHP/00ClIE4BDjtHBgD8jm5nBUVCLj1PBVlwPuH9cxr0XgB6XQRnENoL2DVK+y2IzOpmkjdaXpwHAEqsumF9Qw9Z+dq0gqRDid6fPrrYs9MrpWtWTNcYXU7MmC8c7SVDKv19BAEwdC9QsZYTeWhaXoAEAUOfMX7p2AaiDb7/S/u98FTVdL5P28sAXyTMu+yLOOdd97RnYBGRkYQDAa3/J9XZ69VGuBmiCRJePvtt3VA6u/vN0QWpTJyVD6rWYleVlLw1zeO4EDEo9WdV7Ml3P7gIS0hetq0CyG4ancAzooi9LFYHofnUobcoCFgEULgdDohSZIuRbBVYKnUbNXPblbGWmWYqLS0Ko/OVq1vNcOqw+FoXjctBUY7XPiNils2K9kSOj12rOZKm4q7faKAW87t1H32P56bBWzGr9xv2c7xPF/DsJpIJDSgbWWXq8xaqrXq6OhoagxSzbCaTCa3rMfq6mpNeauZDKvgCF6Z029Qj53HpQO+TTXoUYXhtosiGO04uaar2RIe+tXypi1eQ4ClskRVn+6mp6c3fcTOZrOYnZ3VuQ6e55vOWRgOh2tYRWdnZ7ekx+LiYk0uLhQKNe+2Ek/w4JsndB85bRzuuLj3tDd0qKTgIwe68A8f1l/J//pri0jkzaVLGsawWigUMDk5edrEYCwW0/q2KkVlCW2muN1uXbZdTWwePXr0tJzKa2trOHbsWE2MGAgEmtq8yHEEMys5PFWVNf+t8zpx/4f2gBaUmvYZyhioTHH3+wbw9Y/v1/0sUZBx3y9moZhMl5hiWJ2amtIn1IpFjI+Pw+VyIRgMQhRF8DwPWZaRz+e1duXqk5fD4TDN6Glos/M8uru7EY1GdQCRJAkTExNwu90IBAI6PXK5HOLxOIrFYg0ZpiiKGBwcbH7eysbhDx+bwKHPXQZ7xcWKe64YwHV7QvijH0zg0IksKCs37+3vduHPrhrCdXtCNc+68+F3sZgoaPmtpgILgEb+ODc3pxVwVdDl83nNclUGw9WJREop3G43du3a1TKGVbW1eG5uDoqi6PTI5XKa5arUg+O4ugyrw8PDLUuIHlvL457HJvClj+zV/WxflxtP33UhshJFQVa04Ws1qR+F4Q9/MIHvvbHUkDlZprJ4gUAATqcTs7OzOo7kzfD4McYQDofR09PTkGSimYgmGAzC4/FgdnYW6XRap8dmEqMdHR3o7+83PVvLbFz2lZfnkSyW8J1PnFfr9u0c3Pb6309hDLd++x08emilYcPXBNUFGK1t8TyP0ZERxGIxLK+sQFGUuhl1j
由 ChatGPT 4.1 翻译