{"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在浣熊市狭窄的下水道中,伴随着枪响,那颗本应射中艾达的子弹被浣熊市新晋警察里昂挡了下来。艾达无法理解里昂为什么会为她挡下这发子弹,但她还是将里昂拖到了安全的地方并用绷带治疗了里昂。由于任务在身,艾达不得已丢下了昏迷的里昂,继续去追击G病毒的创造者。当里昂逐渐恢复意识,他发现自己已经是弹尽粮绝,尽管下水道中拥有大量的感染者,但他还是想追上艾达。已知浣熊市下水道的平面图可以简化为一个$$$n$$$行$$$m$$$列的矩阵$$$(3 \\leq n,m \\leq 500)$$$,其中有$$$P$$$个僵尸$$$(0 \\leq P \\leq 50)$$$,所有的这些僵尸会在一个$$$1*k(2 \\leq k \\leq 10)$$$的矩形中来回游走,撕咬所有它们碰到的猎物。好在这些僵尸并不会主动去出击,而只攻击自己闯上门来的倒霉蛋。里昂每次移动都会花费一个单位的时间,而且里昂也不能穿过墙壁、边界或者遇上僵尸,里昂甚至不能够停下,因为一旦停下休息他就没法再站起来。里昂太想赶快追上艾达,请你帮帮他最短需要多长时间才能追上艾达?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行输入4个整数$$$n,m,p,k (3 \\leq n,m \\leq 500, 0 \\leq P \\leq 50, 2 \\leq k \\leq 10)$$$,分别表示矩阵的行、列,僵尸的数量,僵尸来回走动的长度。\u003c/p\u003e\u003cp\u003e第2行到第$$$n+1$$$行输入一个矩阵,每行输入一个字符串,第$$$i$$$个字符串的第$$$j$$$个字符表示矩阵中第$$$i$$$行$$$j$$$列的状态,如果字符是\"#\"表示是可以走的路,如果是\"\u0026amp;\"表示是下水道的墙壁。\u003c/p\u003e\u003cp\u003e第n+2行到第$$$n+p+1$$$行每行输入两个整数$$$x,y$$$和一个字符串,第$$$i$$$行的数据表示第$$$i$$$个僵尸当前时间会从第$$$x$$$行$$$y$$$列出发,沿着固有的方向前进K个单位时间后折返,再走回它之前的位置,再折返,依照这种方法循环下去。第三个字符串表示僵尸行进的方向,\"UP\"表示向上走,\"LEFT\"表示向左走,\"DOWN\"表示向下走,\"RIGHT\"表示向右走。数据保证在k个长度内僵尸不会碰到边界或者墙壁或者两个僵尸路径交错。\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e如果里昂能够追上艾达,输出一行整数,表示里昂最短追上艾达的时间。\u003c/p\u003e\u003cp\u003e如果里昂不能追上艾达,输出一行\"You are Dead!\"(不包含引号)\u003c/p\u003e"}},{"title":"Examples","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 3 1 3\n\u0026amp;\u0026amp;A\n###\n\u0026amp;\u0026amp;L\n2 1 RIGHT\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"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\u003e4 4 1 2\nL#\u0026amp;A\n##\u0026amp;#\n#\u0026amp;##\n####\n3 3 DOWN\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYou are Dead!\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e样例一说明:\u003c/p\u003e\u003cp\u003e如果用*代表僵尸的位置,则起始时状态为 \u003c/p\u003e\u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003e\u0026amp;\u0026amp;A\u003cbr\u003e*##\u003cbr\u003e\u0026amp;\u0026amp;L\u003cbr\u003e\u003c/pre\u003e 一个单位时间后,里昂向上走,僵尸向右走,两者并没有碰上 \u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003e\u0026amp;\u0026amp;A\u003cbr\u003e#*L\u003cbr\u003e\u0026amp;\u0026amp;#\u003cbr\u003e\u003c/pre\u003e 再一个单位时间后,里昂向上走,追上艾达,达成目的。 \u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003e\u0026amp;\u0026amp;L\u003cbr\u003e##*\u003cbr\u003e\u0026amp;\u0026amp;#\u003cbr\u003e\u003c/pre\u003e 样例二说明:\u003cp\u003e初始状态 \u003c/p\u003e\u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003eL#\u0026amp;A\u003cbr\u003e##\u0026amp;#\u003cbr\u003e#\u0026amp;*#\u003cbr\u003e####\u003cbr\u003e\u003c/pre\u003e 一单位时间后 \u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003e##\u0026amp;A\u003cbr\u003eL#\u0026amp;#\u003cbr\u003e#\u0026amp;##\u003cbr\u003e##*#\u003cbr\u003e\u003c/pre\u003e 二单位时间后 \u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003e##\u0026amp;A\u003cbr\u003e##\u0026amp;#\u003cbr\u003eL\u0026amp;*#\u003cbr\u003e####\u003cbr\u003e\u003c/pre\u003e 三单位时间后 \u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003e##\u0026amp;A\u003cbr\u003e##\u0026amp;#\u003cbr\u003e#\u0026amp;##\u003cbr\u003eL#*#\u003cbr\u003e\u003c/pre\u003e 四单位时间后 \u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003e##\u0026amp;A\u003cbr\u003e##\u0026amp;#\u003cbr\u003e#\u0026amp;*#\u003cbr\u003e#L##\u003cbr\u003e\u003c/pre\u003e 里昂如果再向左走的话就会跟僵尸碰个正着,而且不论里昂怎么往回走,在(4,3)总能遇见僵尸,所以里昂挂了。"}}]}