{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\n Thanks to a certain \"green\" resources company, there is a new profitable industry of oil skimming. There are large slicks of crude oil floating in the Gulf of Mexico just waiting to be scooped up by enterprising oil barons. One such oil baron has a special plane that can skim the surface of the water collecting oil on the water\u0027s surface. However, each scoop covers a 10m by 20m rectangle (going either east/west or north/south). It also requires that the rectangle be completely covered in oil, otherwise the product is contaminated by pure ocean water and thus unprofitable! Given a map of an oil slick, the oil baron would like you to compute the maximum number of scoops that may be extracted. The map is an NxN grid where each cell represents a 10m square of water, and each cell is marked as either being covered in oil or pure water.\n\u003c/div\u003e\n\n多亏了某家“绿色”资源公司,才有了一个新的有利可图的原油行业。墨西哥湾漂浮着大量的原油,正等待着富有进取心的石油大亨们的开采。一个这样的石油大亨有一个特殊的飞机,可以掠过水面,在水面上收集石油。然而,每个勺子覆盖一个10米乘20米的矩形(向东/向西或向北/向南)。它还要求矩形完全被油覆盖,否则产品会被纯净的海水污染,从而无利可图!给定一张浮油地图,石油大亨希望你计算出可以提取的最大勺数。地图是一个NxN网格,其中每个单元格代表10平方米的水,每个单元格被标记为覆盖在油或纯水中。"}},{"title":"Input","value":{"format":"HTML","content":"The input starts with an integer K (1 \u0026lt;\u003d K \u0026lt;\u003d 100) indicating the number of cases. Each case starts with an integer N (1 \u0026lt;\u003d N \u0026lt;\u003d 600) indicating the size of the square grid. Each of the following N lines contains N characters that represent the cells of a row in the grid. A character of \u0027#\u0027 represents an oily cell, and a character of \u0027.\u0027 represents a pure water cell."}},{"title":"Output","value":{"format":"HTML","content":"For each case, one line should be produced, formatted exactly as follows: \"Case X: M\" where X is the case number (starting from 1) and M is the maximum number of scoops of oil that may be extracted."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003e1\n6\n......\n.##...\n.##...\n....#.\n....##\n......\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003eCase 1: 3\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}