{"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 Harry: \"But Hagrid. How am I going to pay for all of this? I haven\u0027t any money.\" \u003cbr\u003e Hagrid: \"Well there\u0027s your money, Harry! Gringotts, the wizard bank! Ain\u0027t no safer place. Not one. Except perhaps Hogwarts.\" \u003cbr\u003e — Rubeus Hagrid to Harry Potter. \u003cbr\u003e\u0026nbsp;\u0026nbsp;Gringotts Wizarding Bank is the only bank of the wizarding world, and is owned and operated by goblins. It was created by a goblin called Gringott. Its main offices are located in the North Side of Diagon Alley in London, England. In addition to storing money and valuables for wizards and witches, one can go there to exchange Muggle money for wizarding money. The currency exchanged by Muggles is later returned to circulation in the Muggle world by goblins. According to Rubeus Hagrid, other than Hogwarts School of Witchcraft and Wizardry, Gringotts is the safest place in the wizarding world.\u003cbr\u003e\u0026nbsp;\u0026nbsp;The text above is quoted from Harry Potter Wiki. But now Gringotts Wizarding Bank is not safe anymore. The stupid Dudley, Harry Potter\u0027s cousin, just robbed the bank. Of course, uncle Vernon, the drill seller, is behind the curtain because he has the most advanced drills in the world. Dudley drove an invisible and soundless drilling machine into the bank, and stole all Harry Potter\u0027s wizarding money and Muggle money. Dumbledore couldn\u0027t stand with it. He ordered to put some magic lights in the bank rooms to detect Dudley\u0027s drilling machine. The bank can be considered as a N × M grid consisting of N × M rooms. Each room has a coordinate. The coordinates of the upper-left room is (1,1) , the down-right room is (N,M) and the room below the upper-left room is (2,1)..... A 3×4 bank grid is shown below:\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/de7cbf2fbbe60d84487a2c9ea9e49149?v\u003d1715565086\"\u003e\u003c/center\u003e \u003cbr\u003e Some rooms are indestructible and some rooms are vulnerable. Dudely\u0027s machine can only pass the vulnerable rooms. So lights must be put to light up all vulnerable rooms. There are at most fifteen vulnerable rooms in the bank. You can at most put one light in one room. The light of the lights can penetrate the walls. If you put a light in room (x,y), it lights up three rooms: room (x,y), room (x-1,y) and room (x,y+1). Dumbledore has only one special light whose lighting direction can be turned by 0 degree,90 degrees, 180 degrees or 270 degrees. For example, if the special light is put in room (x,y) and its lighting direction is turned by 90 degrees, it will light up room (x,y), room (x,y+1 ) and room (x+1,y). Now please help Dumbledore to figure out at least how many lights he has to use to light up all vulnerable rooms.\u003cbr\u003e Please pay attention that you can\u0027t light up any indestructible rooms, because the goblins there hate light. \u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":" There are several test cases.\u003cbr\u003e In each test case:\u003cbr\u003e The first line are two integers N and M, meaning that the bank is a N × M grid(0\u0026lt;N,M \u0026lt;\u003d 200).\u003cbr\u003e Then a N×M matrix follows. Each element is a letter standing for a room. \u0027#\u0027 means a indestructible room, and \u0027.\u0027 means a vulnerable room. \u003cbr\u003e The input ends with N \u003d 0 and M \u003d 0\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":" For each test case, print the minimum number of lights which Dumbledore needs to put.\u003cbr\u003e If there are no vulnerable rooms, print 0.\u003cbr\u003e If Dumbledore has no way to light up all vulnerable rooms, print -1."}},{"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\u003e2 2\r\n##\r\n##\r\n2 3\r\n#..\r\n..#\r\n3 3\r\n###\r\n#.#\r\n###\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n2\r\n-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}