{"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×M网格,由N×M个房间组成。每个房间都有一个坐标。左上角房间的坐标是(1,1),右下角房间是(N,M),左上角房间下方的房间是(2,1)…… 一个3×4的银行网格如下所示:\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/00e39508a961e23ed2da15ef6ef9264a?v\u003d1707034170\"\u003e\u003c/center\u003e \u003cbr\u003e\u003cbr\u003e 一些房间是坚不可摧的,一些房间是脆弱的。地精们总是更关心自己的安全,而不是顾客的财产,所以他们住在坚不可摧的房间,并把顾客的财产放在脆弱的房间里。哈利·波特的宝贝也被放在一些脆弱的房间里。达德利想要在这个假期偷走哈利的东西。他从他父亲、弗农叔叔那里得到了最先进的钻机,然后钻进了银行。但他只能通过脆弱的房间。他无法进入坚不可摧的房间。他从某个脆弱的房间开始,然后向四个方向移动:北、东、南和西。达德利知道哈利的宝贝在哪里。他想尽量少地走几步来收集哈利的宝贝。从一个房间移动到另一个相邻的房间被称为“一步”。达德利不想在收集完所有哈利的东西之前离开银行。达德利很笨。他付给你100万美元,希望你至少能够算出他必须走多少步才能收集到所有哈利的宝贝。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":" 有几个测试用例。\u003cbr\u003e 在每个测试用例中:\u003cbr\u003e 第一行是两个整数N和M,表示银行是一个N×M的网格(0\u003cN,M\u003c\u003d100)。\u003cbr\u003e 然后是一个N×M的矩阵。每个元素是一个代表一个房间的字母。\u0027#\u0027表示一个坚不可摧的房间,\u0027.\u0027表示一个脆弱的房间,而唯一的\u0027@\u0027表示达德利开始移动的脆弱的房间。\u003cbr\u003e 接下来一行是一个整数K (0\u003cK\u003c\u003d4),表示银行里有K个哈利·波特的宝贝。\u003cbr\u003e 接下来的K行,每行描述一个哈利·波特的宝贝的位置,用两个整数X和Y表示,表示房间(X,Y)里有一个宝贝。\u003cbr\u003e 当N\u003d0且M\u003d0时输入结束\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":" 对于每个测试用例,打印达德利必须走的最小步数。如果达德利无法得到所有哈利的东西,则打印-1。\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\u003e2 3\r\n##@\r\n#.#\r\n1\r\n2 2\r\n4 4\r\n#@##\r\n....\r\n####\r\n....\r\n2\r\n2 1\r\n2 4\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\r\n5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}