{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cdiv\u003e\n 4月16日,日本熊本地区强震后,受灾严重的阿苏市一养猪场倒塌,幸运的是,猪圈里很多头猪依然坚强存活。当地15名消防员耗时一天解救围困的“猪坚强”。不过与在废墟中靠吃木炭饮雨水存活36天的中国汶川“猪坚强”相比,熊本的猪可没那么幸运,因为它们最终还是没能逃过被送往屠宰场的命运。\n \u003c/div\u003e \n \u003cdiv\u003e\u003c/div\u003e \n \u003cdiv\u003e\n 我们假设“猪坚强”被困在一个N*M的废墟中,其中“@”表示“猪坚强”的位置,“.”表示可以直接通过的空地,“#”表示不能拆毁的障碍物,“*”表示可以拆毁的障碍物,那么请问消防员至少要拆毁多少个障碍物,才能从废墟中救出“猪坚强”送往屠宰场?(当“猪坚强”通过空地或被拆毁的障碍物移动到废墟边缘时,视作被救出废墟)\n \u003c/div\u003e \n \u003cdiv\u003e\u003c/div\u003e \n \u003cp\u003e\u003c/p\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cdiv\u003e\n 多组数据,第一行有一个整数T,表示有T组数据。(T\u0026lt;\u003d100)\n \u003c/div\u003e \n \u003cdiv\u003e\n 以下每组数据第一行有两个整数N和M。(1\u0026lt;\u003dN,M\u0026lt;\u003d100)\n \u003c/div\u003e \n \u003cdiv\u003e\n 接着N行,每行有一个长度为M的字符串。\n \u003c/div\u003e \n \u003cp\u003e\u003c/p\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\n \u003cp\u003e一个整数,为最少拆毁的障碍物数量,如果不能逃离废墟,输出-1。\u003c/p\u003e \n \u003cp\u003e\u003c/p\u003e\n \u003c/body\u003e\n\u003c/html\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e3\n3 3\n###\n#@*\n***\n3 4\n####\n#@.*\n**.*\n3 3\n.#.\n#@#\n.#.\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e1\n0\n-1\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003chtml\u003e\n \u003chead\u003e\u003c/head\u003e\n \u003cbody\u003e\u003c/body\u003e\n\u003c/html\u003e"}}]}