{"trustable":true,"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行n列的方形板,每一行和每一列代表一条街道或一堵墙。\u003cbr\u003e\u003cbr\u003e一个碉堡是一个有四个开口可以射击的小城堡。这四个开口分别朝北、东、南和西。每个开口都会有一挺机枪射击。\u003cbr\u003e\u003cbr\u003e在这里我们假设子弹的威力足以穿越任何距离并摧毁它路过的碉堡。另一方面,墙壁建造得非常坚固,可以挡住子弹。\u003cbr\u003e\u003cbr\u003e目标是在城市中尽可能多地放置碉堡,使得任何两个碉堡都不能互相摧毁。合法的碉堡配置是指除非至少有一堵墙将它们隔开,否则在地图上没有两个碉堡在同一水平行或垂直列上。在这个问题中,我们将考虑包含子弹无法穿过的墙壁的小正方形城市(最多4x4)。\u003cbr\u003e\u003cbr\u003e以下图片显示了同一个棋盘的五幅图片。第一幅图片是空棋盘,第二和第三幅图片显示了合法的配置,第四和第五幅图片显示了非法的配置。对于这个棋盘,合法配置中最多的碉堡数量是5;第二幅图片展示了一种方法,但还有其他几种方法。\u003cbr\u003e\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/c7a929be1ccf07570c6d0f5d5e9fed22?v\u003d1711307992\"\u003e\u003cbr\u003e\u003cbr\u003e你的任务是编写一个程序,给定一个地图描述,计算在合法配置中可以放置的最大碉堡数量。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入文件包含一个或多个地图描述,后面跟着一行包含数字0,表示文件结束。每个地图描述以包含一个正整数n的行开始,n是城市的大小;n最多为4。接下来的n行描述地图的每一行,用\u0027.\u0027表示空地,用大写字母\u0027X\u0027表示墙壁。输入文件中没有空格。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行,包含在合法配置中可以放置的最大碉堡数量。\u003cbr\u003e"}},{"title":"样例","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\u003e4\r\n.X..\r\n....\r\nXX..\r\n....\r\n2\r\nXX\r\n.X\r\n3\r\n.X.\r\nX.X\r\n.X.\r\n3\r\n...\r\n.XX\r\n.XX\r\n4\r\n....\r\n....\r\n....\r\n....\r\n0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n1\r\n5\r\n2\r\n4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}