{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e爱丽丝生活在一个可以被建模为大小为$$$n \\times n$$$的正方形网格的平面上,行和列从$$$1$$$到$$$n$$$编号。我们用有序对$$$(r, c)$$$表示第$$$r$$$行和第$$$c$$$列的交叉处的单元格。网格中的每个单元格要么是\u003cspan class\u003d\"tex-font-style-it\"\u003e陆地\u003c/span\u003e,要么是\u003cspan class\u003d\"tex-font-style-it\"\u003e水域\u003c/span\u003e。\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/f2415e746cbd0ef196e6f8ca6b13327f?v\u003d1701176267\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"265px\"\u003e \u003cspan class\u003d\"tex-font-size-small\"\u003e一个包含$$$n \u003d 5$$$的示例行星。它也出现在第一个示例测试中。\u003c/span\u003e \u003c/center\u003e\u003cp\u003e爱丽丝居住在\u003cspan class\u003d\"tex-font-style-it\"\u003e陆地\u003c/span\u003e单元格$$$(r_1, c_1)$$$中。她希望前往\u003cspan class\u003d\"tex-font-style-it\"\u003e陆地\u003c/span\u003e单元格$$$(r_2, c_2)$$$。在任何时刻,她可以移动到她所在位置相邻的单元格中的一个,即上、下、左或右四个方向中的一个。\u003c/p\u003e\u003cp\u003e不幸的是,爱丽丝不会游泳,除了步行(即她只能在\u003cspan class\u003d\"tex-font-style-it\"\u003e陆地\u003c/span\u003e上行走)之外,没有其他可行的交通方式。因此,爱丽丝的旅行可能是不可能的。\u003c/p\u003e\u003cp\u003e为了帮助爱丽丝,你计划在某两个\u003cspan class\u003d\"tex-font-style-it\"\u003e陆地\u003c/span\u003e单元格之间最多创建\u003cspan class\u003d\"tex-font-style-bf\"\u003e一个\u003c/span\u003e隧道。隧道将允许爱丽丝自由地在两个端点之间移动。确实,创建隧道需要付出很大的努力:在单元格$$$(r_s, c_s)$$$和$$$(r_t, c_t)$$$之间创建隧道的成本是$$$(r_s-r_t)^2 + (c_s-c_t)^2$$$。\u003c/p\u003e\u003cp\u003e目前,你的任务是找到创建最多一个隧道的最小可能成本,以便爱丽丝能够从$$$(r_1, c_1)$$$到$$$(r_2, c_2)$$$旅行。如果不需要创建隧道,则成本为$$$0$$$。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数$$$n$$$($$$1 \\leq n \\leq 50$$$)—正方形网格的宽度。\u003c/p\u003e\u003cp\u003e第二行包含两个以空格分隔的整数$$$r_1$$$和$$$c_1$$$($$$1 \\leq r_1, c_1 \\leq n$$$)—表示爱丽丝所在的单元格。\u003c/p\u003e\u003cp\u003e第三行包含两个以空格分隔的整数$$$r_2$$$和$$$c_2$$$($$$1 \\leq r_2, c_2 \\leq n$$$)—表示爱丽丝希望前往的单元格。\u003c/p\u003e\u003cp\u003e接下来的$$$n$$$行每行包含$$$n$$$个字符的字符串。第$$$j$$$行的第$$$i$$$个字符($$$1 \\leq i, j \\leq n$$$)是\u003cspan class\u003d\"tex-font-style-tt\"\u003e0\u003c/span\u003e,如果$$$(i, j)$$$是\u003cspan class\u003d\"tex-font-style-it\"\u003e陆地\u003c/span\u003e,或者是\u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e,如果$$$(i, j)$$$是\u003cspan class\u003d\"tex-font-style-it\"\u003e水域\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e保证$$$(r_1, c_1)$$$和$$$(r_2, c_2)$$$是\u003cspan class\u003d\"tex-font-style-it\"\u003e陆地\u003c/span\u003e。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数,表示创建最多一个隧道的最小可能成本,以便爱丽丝能够从$$$(r_1, c_1)$$$到$$$(r_2, c_2)$$$旅行。\u003c/p\u003e"}},{"title":"示例 1","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\u003e5\n1 1\n5 5\n00001\n11111\n00111\n00110\n00110\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例 2","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\u003e3\n1 3\n3 1\n010\n101\n010\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,应该创建一个连接单元格$$$(1, 4)$$$和$$$(4, 5)$$$的隧道。这样做的成本是$$$(1-4)^2 + (4-5)^2 \u003d 10$$$,这是最优的。这样,爱丽丝可以从$$$(1, 1)$$$到$$$(1, 4)$$$步行,从$$$(1, 4)$$$到$$$(4, 5)$$$使用隧道,最后从$$$(4, 5)$$$到$$$(5, 5)$$$步行。\u003c/p\u003e\u003cp\u003e在第二个示例中,显然需要创建连接单元格$$$(1, 3)$$$和$$$(3, 1)$$$的隧道。这样做的成本是$$$(1-3)^2 + (3-1)^2 \u003d 8$$$。\u003c/p\u003e"}}]}