{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\r\n\u003ctable class\u003d\"problems\" width\u003d\"100%\"\u003e\u003ctbody\u003e\u003ctr class\u003d\"navigation\"\u003e\r\n\u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/MLASERP/en/\"\u003eEnglish\u003c/a\u003e\u003c/td\u003e \r\n\u003ctd width\u003d\"50%\"\u003e\u003ca href\u003d\"https://www.spoj.com/problems/MLASERP/vn/\"\u003eVietnamese\u003c/a\u003e\u003c/td\u003e \r\n\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\r\n\u003cp\u003e \u003c/p\u003e\r\n\r\n\r\n\u003cp\u003eThe cows have a new laser-based system so they can have casual\r\nconversations while out in the pasture which is modelled as a W × H\r\ngrid of points (1 \u0026lt;\u003d W \u0026lt;\u003d 100; 1 \u0026lt;\u003d H \u0026lt;\u003d 100).\u003c/p\u003e\r\n\r\n\u003cp\u003eThe system requires a sort of line-of-sight connectivity in order\r\nto sustain communication. The pasture, of course, has rocks and\r\ntrees that disrupt the communication but the cows have purchased\r\ndiagonal mirrors (\u0027/\u0027 and \u0027\\\u0027 below) that deflect the laser beam\r\nthrough a 90 degree turn. Below is a map that illustrates the\r\nproblem.\u003c/p\u003e\r\n\r\n\u003cp\u003eH is 8 and W is 7 for this map. The two communicating cows are\r\nnotated as \u0027C\u0027s; rocks and other blocking elements are notated as\r\n\u0027*\u0027s:\u003c/p\u003e\r\n\u003cpre\u003e\r\n7 . . . . . . . 7 . . . . . . .\r\n6 . . . . . . C 6 . . . . . /-C\r\n5 . . . . . . * 5 . . . . . | *\r\n4 * * * * * . * 4 * * * * * | *\r\n3 . . . . * . . 3 . . . . * | .\r\n2 . . . . * . . 2 . . . . * | .\r\n1 . C . . * . . 1 . C . . * | .\r\n0 . . . . . . . 0 . \\-------/ .\r\n 0 1 2 3 4 5 6 0 1 2 3 4 5 6\r\n\u003c/pre\u003e\r\n\u003cp\u003eDetermine the minimum number of mirrors M that must be installed\r\nto maintain laser communication between the two cows, a feat which\r\nis always possible in the given test data.\u003c/p\u003e\u003cp\u003e\r\n\r\n\u003c/p\u003e\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eLine 1: Two space separated integers: W and H.\u003c/li\u003e\r\n\u003cli\u003eLines 2..H+1: The entire pasture.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eLine 1: A single integer: M.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e7 8\r\n.......\r\n......C\r\n......*\r\n*****.*\r\n....*..\r\n....*..\r\n.C..*..\r\n.......\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\u003cb\u003eAny suggested test case will be welcomed.\u003c/b\u003e\r\n\r\n\r\n \r\n\u003c/div\u003e"}}]}