{"trustable":false,"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":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003eAlice生活在一个平坦的星球上,可以将这个星球的地面划分为大小为$$$n$$$行$$$n$$$列的正方形网格(行与列各自用从$$$1$$$到$$$n$$$的整数进行编号),于是可以使用二元组$$$(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\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" height\u003d\"264px\" SRC\u003d\"CDN_BASE_URL/d3b42b68be6152bf09875978ebb726e8?v\u003d1551445906\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"264px\"\u003e \n \u003cspan class\u003d\"tex-font-size-small\"\u003e这是一个$$$n \u003d 5$$$的星球(这也正是第一个输入样例)。\u003c/span\u003e \n\u003c/center\u003e\n\u003cp\u003eAlice居住在$$$(r_1, c_1)$$$这个\u003cspan class\u003d\"tex-font-style-it\"\u003e陆地\u003c/span\u003e方格区域上.。某一天,她想去$$$(r_2, c_2)$$$这个\u003cspan class\u003d\"tex-font-style-it\"\u003e陆地\u003c/span\u003e方格区域。由于某种不可抗力,在任意时刻,她只能够从自己所在的方格区域前往相邻的方格区域(换句话说就是上、下、左、右这四个单元)。\u003c/p\u003e\n\u003cp\u003e不幸的是,Alice不会游泳,水边也没有任何交通工具可以供她使用,于是她只能在\u003cspan class\u003d\"tex-font-style-bf\"\u003e陆地\u003c/span\u003e上移动。也正因此,她可能无法到达自己想去的地方。\u003c/p\u003e\n\u003cp\u003e为了帮助Alice,你可以修建\u003cspan class\u003d\"tex-font-style-bf\"\u003e最多一个\u003c/span\u003e隧道,将将两块\u003cspan class\u003d\"tex-font-style-it\"\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\n\u003cp\u003e现在,你需要修建最多一个隧道使得爱丽丝可以从$$$(r_1, c_1)$$$前往$$$(r_2, c_2)$$$区域,同时,你也应当保证花费最小,\u003cspan class\u003d\"tex-font-style-it\"\u003e注意\u003c/span\u003e,如果不需要修建隧道,那么花费将是$$$0$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e输入数据的第一行是一个正整数 $$$n$$$ ($$$1 \\leq n \\leq 50$$$) — 表示这个方形网格的大小。\u003c/p\u003e\n\u003cp\u003e第二行包含两个使用空格分割的正整数$$$r_1$$$和$$$c_1$$$ ($$$1 \\leq r_1, c_1 \\leq n$$$) — 表示Alice居住的地方。\u003c/p\u003e\n\u003cp\u003e第三行也包含两个使用空格分割的正整数$$$r_2$$$和$$$c_2$$$ ($$$1 \\leq r_2, c_2 \\leq n$$$) — 表示Alice想去的地方。\u003c/p\u003e\n\u003cp\u003e接下来输入$$$n$$$行,且每行有$$$n$$$列有效字符(0和1),如果区域$$$(i, j)$$$是陆地,这个方阵的第$$$i$$$行第$$$j$$$列上的字符是\u003cspan class\u003d\"tex-font-style-tt\"\u003e0\u003c/span\u003e ,相应地,如果这个区域是水,则用\u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e表示。\u003c/p\u003e\n\u003cp\u003e输入数据保证起点和终点都是陆地,因此通过修建隧道总是能让问题有解。\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e请输出修建隧道的花费(不用修建隧道则输出0)\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e5\n1 1\n5 5\n00001\n11111\n00111\n00110\n00110\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e10\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e3\n1 3\n3 1\n010\n101\n010\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e8\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample, a tunnel between cells $$$(1, 4)$$$ and $$$(4, 5)$$$ should be created. The cost of doing so is $$$(1-4)^2 + (4-5)^2 \u003d 10$$$, which is optimal. This way, Alice could walk from $$$(1, 1)$$$ to $$$(1, 4)$$$, use the tunnel from $$$(1, 4)$$$ to $$$(4, 5)$$$, and lastly walk from $$$(4, 5)$$$ to $$$(5, 5)$$$.\u003c/p\u003e\n\u003cp\u003eIn the second sample, clearly a tunnel between cells $$$(1, 3)$$$ and $$$(3, 1)$$$ needs to be created. The cost of doing so is $$$(1-3)^2 + (3-1)^2 \u003d 8$$$.\u003c/p\u003e"}}]}