{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003ccenter\u003e\n\t\u003cimg src\u003d\"CDN_BASE_URL/8f455915740e1a81600842e37745fd34?v\u003d1720300291\"\u003e\u003cbr\u003e\n\tTom\u0027s Meadow\u003cbr\u003e\n\u003c/center\u003e\n\u003cp\u003e\n 汤姆在他的花园里有一片草地。他把它分成了 \u003ci\u003eN\u003c/i\u003e * \u003ci\u003eM\u003c/i\u003e 个方块。\n最初所有的方块都被草覆盖着,有些方块可能无法被割草(我们称之为禁止方块)。\n他想要割掉一些方块上的草。\n他必须遵守以下所有规则:\u003cbr\u003e\n\u003c/p\u003e\n\n\u003cp\u003e\n\u003cb\u003e\n1 他可以从任何可以被割草的方块开始。\u003cbr\u003e\n2 他可以在任何可以被割草的方块结束。\u003cbr\u003e\n3 割草完一个方块后,他可以进入其中一个相邻方块。\u003cbr\u003e\n4 他不能进入任何禁止方块。\u003cbr\u003e\n5 他不能进入他已经割过草的方块。\u003cbr\u003e\n6 如果他在某个方块上,他必须先割草(然后决定是否割相邻方块)。\u003cbr\u003e\n7 每个可以被割草的方块都有一个名为美丽度 \u003ci\u003eD\u003c/i\u003e 的属性(\u003ci\u003eD\u003c/i\u003e 是正整数),如果他割了这个方块,草地的美丽度会增加 \u003ci\u003eD\u003c/i\u003e。\u003cbr\u003e\n8 请注意,草地的美丽度一开始是0。\u003cbr\u003e\n9 当然,在他决定结束之前,他不能离开草地。\u003cbr\u003e\n\u003c/b\u003e\n 两个方块如果共享一条边则它们是相邻的。\n\u003c/p\u003e\n\n\u003cp\u003e\n问题来了。在不违反上述规则的情况下,汤姆的草地最大美丽度是多少。\n\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003e输入\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\n这个问题有多个测试用例。\n输入的第一行是一个整数 \u003ci\u003eT\u003c/i\u003e(1 \u0026lt;\u003d \u003ci\u003eT\u003c/i\u003e \u0026lt; 60),表示测试用例的数量。接下来是 \u003ci\u003eT\u003c/i\u003e 个连续的测试用例。\n每个测试用例的第一行是包含两个整数 \u003ci\u003eN\u003c/i\u003e(1 \u0026lt;\u003d \u003ci\u003eN\u003c/i\u003e \u0026lt; 8)和 \u003ci\u003eM\u003c/i\u003e(1 \u0026lt;\u003d \u003ci\u003eM\u003c/i\u003e \u0026lt; 8)的单独一行,表示草地的行数和列数。\n然后是 \u003ci\u003eN\u003c/i\u003e 行输入,描述草地的各行。\n每一行包含 \u003ci\u003eM\u003c/i\u003e 个以空格分隔的整数 \u003ci\u003eD\u003c/i\u003e(0 \u0026lt;\u003d \u003ci\u003eD\u003c/i\u003e \u0026lt;\u003d 60000),表示对应方块的美丽度。\n\u003cb\u003e\n 为简单起见,禁止方块的美丽度为0。(当然,汤姆不能进入或割这些方块。)\n\u003c/b\u003e\n\u003c/p\u003e\n\n\n\u003cp\u003e\u003cb\u003e输出\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\n对于每个测试用例,输出一个整数,表示最后草地的最大美丽度。\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003e样例输入\u003c/b\u003e\u003c/p\u003e\n\u003cpre\u003e2\n1 1\n10\n1 2\n5 0\n\u003c/pre\u003e\n\u003cp\u003e\u003cb\u003e样例输出\u003c/b\u003e\u003c/p\u003e\n\u003cpre\u003e10\n5\n\u003c/pre\u003e"}}]}