{"id":1956,"date":"2016-04-07T11:48:19","date_gmt":"2016-04-07T03:48:19","guid":{"rendered":"http:\/\/boweihe.me\/?p=1956"},"modified":"2016-04-07T11:48:19","modified_gmt":"2016-04-07T03:48:19","slug":"m-2016-%e9%a2%98%e7%9b%ae3-demo-day","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1956","title":{"rendered":"M$ 2016 \u9898\u76ee3 : Demo Day"},"content":{"rendered":"
\n
\u65f6\u95f4\u9650\u5236:10000ms<\/div>\n
\u5355\u70b9\u65f6\u9650:1000ms<\/div>\n
\u5185\u5b58\u9650\u5236:256MB<\/div>\n<\/div>\n
\n

\u63cf\u8ff0<\/h3>\n

You work as an intern at a robotics startup. Today is your company’s demo day. During the demo your company’s robot will be put in a maze and without any information about the maze, it should be able to find a way out.
\nThe maze consists of N * M grids. Each grid is either empty(represented by ‘.’) or blocked by an obstacle(represented by ‘b’). The robot will be release at the top left corner and the exit is at the bottom right corner.
\nUnfortunately some sensors on the robot go crazy just before the demo starts. As a result, the robot can only repeats two operations alternatively: keep moving to the right until it can’t and keep moving to the bottom until it can’t. At the beginning, the robot keeps moving to the right.<\/p>\n

rrrrbb..\n...r....     ====> The robot route with broken sensors is marked by 'r'.\n...rrb..\n...bb...\n<\/pre>\n
While the FTEs(full-time employees) are busy working on the sensors, you try to save the demo day by rearranging the maze in such a way that even with the broken sensors the robot can reach the exit successfully. You can change a grid from empty to blocked and vice versa. So as not to arouse suspision, you want to change as few grids as possible. What is the mininum number?<\/p>\n
\u8f93\u5165<\/h3>\n
Line 1: N, M.
\nLine 2-N+1: the N * M maze.
\nFor 20% of the data, N * M <= 16.
\nFor 50% of the data, 1 <= N, M <= 8.
\nFor 100% of the data, 1<= N, M <= 100.<\/p>\n
\u8f93\u51fa<\/h3>\n
The minimum number of grids to be changed.\n<\/p><\/div>\n
\u6ce8\u8bb0\uff1a<\/h3>\n
\u52a8\u6001\u89c4\u5212\u7684\u4e00\u9053\u9898\uff0c\u540e\u6094\u5f53\u65f6\u6ca1\u6709\u770b\u901a\u8fc7\u7387\u5148\u505a\u4e86\u7b2c\u4e8c\u9053\uff0c\u7b2c\u4e8c\u9898\u6ca1\u6709\u719f\u7ec3\u638c\u63e1Trie\u7ed3\u679c\u5904\u7406\u8d85\u65f6\u4e86\uff01
\n\u8fd9\u9898\u5c31\u662f\u72b6\u6001\u9ebb\u70e6\u70b9\uff0c\u6211\u7684\u5904\u7406\u65b9\u5f0f\u662f\u5728\u5f53\u524d\u4f4d\u7f6e\u5c31\u5224\u65ad\u53f3\u4fa7\u53ca\u4e0b\u4fa7\u7684\u901a\u884c\u60c5\u51b5\uff0c\u5fc5\u8981\u65f6\u505a\u51fa\u6539\u53d8\uff0c\u7136\u540e\u7ee7\u7eed\u3002\u56e0\u6b64\u6ce8\u610f\u70b9\u662f\u4e00\u5f00\u59cb\u5c31\u88ab[0][0]\u4f4d\u7f6eblocked\u7684\u60c5\u51b5\u3002
\n\u4ee5(x\u4f4d\u7f6e,y\u4f4d\u7f6e,\u5f53\u524d\u65b9\u5411)\u4e3a\u4e00\u4e2a\u4e09\u5143\u7ec4\uff0c\u53ef\u4ee5\u4fdd\u5b58\u552f\u4e00\u7684\u72b6\u6001\u7ed3\u679c\uff0c\u907f\u514d\u91cd\u590d\u9012\u5f52\u3002<\/p>\n
\u4ee3\u7801:<\/h3>\n
\u672a\u7ecf\u8be6\u7ec6\u6d4b\u8bd5\uff0c\u5f85\u6d4b\u8bd5\uff01\u611f\u89c9\u81ea\u5df1\u7684\u7f16\u7801\u80fd\u529b\u8fd8\u662f\u6709\u9650\uff0c\u6b22\u8fce\u8fc7\u5ba2\u63d0\u51fa\u610f\u89c1\u3002<\/span><\/p>\n
#include <iostream>\n#include <vector>\n#include <string>\nusing namespace std;\nconst int FAIL = -32767;\nstruct St {\n\tbool hasRight;\n\tbool hasDown;\n\tint rightBest;\n\tint downBest;\n\tSt(){\n\t\thasRight = false;\n\t\thasDown = false;\n\t}\n\tvoid setVal(bool movR, int val) {\n\t\tif (movR) {\n\t\t\thasRight = true;\n\t\t\trightBest = val;\n\t\t}\n\t\telse {\n\t\t\thasDown = true;\n\t\t\tdownBest = val;\n\t\t}\n\t}\n\tbool hasVal(bool movR) {\n\t\tif (movR)\n\t\t\treturn hasRight;\n\t\telse\n\t\t\treturn hasDown;\n\t}\n\tint getVal(bool movR) {\n\t\tif (movR)\n\t\t\treturn rightBest;\n\t\telse\n\t\t\treturn downBest;\n\t}\n};\nint legalMin(int x, int y) {\n\tif (x < 0) return y;\n\telse if (y < 0) return x;\n\telse return x<y ? x : y;\n}\nint moveMaze(const vector<string>& maze, int i, int j, bool movR, vector<vector<St>>& storedMap) {\n\t\/\/cout << '.';\n\tif ((i == maze.size() - 1) && (j == maze[0].size() - 1)) {\n\t\t\/\/Out of maze and finished\n\t\treturn 0;\n\t}\n\telse if ((i == maze.size()) || (j == maze[0].size())) {\n\t\t\/\/Reach boundary\n\t\treturn FAIL;\n\t}\n\tif (storedMap[i][j].hasVal(movR)) {\n\t\t\/\/cout << \"HIT!\" << i << \", \" << j << \", \"<< movR << endl;\n\t\treturn storedMap[i][j].getVal(movR);\n\t}\n\tint right = FAIL;\n\tint down = FAIL;\n\tif (movR) {\n\t\t\/\/Moving towards right side\n\t\tif (j == maze[0].size() - 1 || maze[i][j + 1] == '.') {\n\t\t\tright = moveMaze(maze, i, j + 1, movR, storedMap);\n\t\t\tif (j == maze[0].size() - 1)\n\t\t\t\tdown = moveMaze(maze, i + 1, j, false, storedMap);\n\t\t\telse\n\t\t\t\tdown = 1 + moveMaze(maze, i + 1, j, false, storedMap);\n\t\t}\n\t\telse {\n\t\t\t\/\/blocked\n\t\t\tright = 1 + moveMaze(maze, i, j + 1, movR, storedMap);\n\t\t\tif (i == maze.size() - 1 || maze[i + 1][j] == '.')\n\t\t\t\tdown = moveMaze(maze, i + 1, j, false, storedMap);\n\t\t\telse\n\t\t\t\tdown = 1 + moveMaze(maze, i + 1, j, false, storedMap);\n\t\t}\n\t}\n\telse {\n\t\tif (i == maze.size() - 1 || maze[i + 1][j] == '.') {\n\t\t\t\/\/Move down safely\n\t\t\tdown = moveMaze(maze, i + 1, j, movR, storedMap);\n\t\t\tif (i == maze.size() - 1)\n\t\t\t\tright = moveMaze(maze, i, j + 1, true, storedMap);\n\t\t\telse\n\t\t\t\tright = 1 + moveMaze(maze, i, j + 1, true, storedMap);\n\t\t}\n\t\telse {\n\t\t\t\/\/blocked\n\t\t\tdown = 1 + moveMaze(maze, i + 1, j, movR, storedMap);\n\t\t\tif (j == maze[0].size() - 1 || maze[i][j + 1] == '.')\n\t\t\t\tright = moveMaze(maze, i, j + 1, true, storedMap);\n\t\t\telse\n\t\t\t\tright = 1 + moveMaze(maze, i, j + 1, true, storedMap);\n\t\t}\n\t}\n\tint result = legalMin(down, right);\n\tstoredMap[i][j].setVal(movR, result);\n\treturn result;\n}\nint main() {\n\tint N, M;\n\tcin >> N >> M;\n\tvector<string> maze;\n\tfor (int i = 0; i<N; i++) {\n\t\tstring str;\n\t\tcin >> str;\n\t\tmaze.push_back(str);\n\t}\n\tvector<vector<St>> storedMap;\n\tfor (int i = 0; i < N; i++) {\n\t\tvector<St> line;\n\t\tfor (int j = 0; j < M; j++) {\n\t\t\tline.push_back(St());\n\t\t}\n\t\tstoredMap.push_back(line);\n\t}\n\tint result;\n\tif(maze[0][0] == '.')\n\t\tresult = moveMaze(maze, 0, 0, true, storedMap);\n\telse \/\/[0][0]\u5c31\u662f'b'\n\t\tresult = 1 + moveMaze(maze, 0, 0, true, storedMap);\n\tcout << result << endl;\n\treturn 0;\n}<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
\u65f6\u95f4\u9650\u5236:10000ms \u5355\u70b9\u65f6\u9650:1000ms \u5185\u5b58\u9650\u5236:256MB \u63cf\u8ff0 You work as an intern at a robotics startup. Today is your company’s demo day. During the demo your company’s robot will be put in a maze and without any information about the maze, it should be able to find a way out. The maze consists of N * M grids. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[141,183],"class_list":["post-1956","post","type-post","status-publish","format-standard","hentry","category-study","tag-141","tag-183"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1956","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1956"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1956\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1956"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1956"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1956"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}