{"id":7994,"date":"2021-01-17T14:10:36","date_gmt":"2021-01-17T22:10:36","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7994"},"modified":"2021-01-17T14:11:41","modified_gmt":"2021-01-17T22:11:41","slug":"leetcode-1728-cat-and-mouse-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1728-cat-and-mouse-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1728. Cat and Mouse II"},"content":{"rendered":"\n
A game is played by a cat and a mouse named Cat and Mouse.<\/p>\n\n\n\n
The environment is represented by a grid<\/code> of size rows x cols<\/code>, where each element is a wall, floor, player (Cat, Mouse), or food.<\/p>\n\n\n\n
Players are represented by the characters 'C'<\/code>(Cat),'M'<\/code>(Mouse).<\/li>
Floors are represented by the character '.'<\/code> and can be walked on.<\/li>
Walls are represented by the character '#'<\/code> and cannot be walked on.<\/li>
Food is represented by the character 'F'<\/code> and can be walked on.<\/li>
There is only one of each character 'C'<\/code>, 'M'<\/code>, and 'F'<\/code> in grid<\/code>.<\/li><\/ul>\n\n\n\n
Mouse and Cat play according to the following rules:<\/p>\n\n\n\n
Mouse moves first<\/strong>, then they take turns to move.<\/li>
During each turn, Cat and Mouse can jump in one of the four directions (left, right, up, down). They cannot jump over the wall nor outside of the grid<\/code>.<\/li>
catJump, mouseJump<\/code> are the maximum lengths Cat and Mouse can jump at a time, respectively. Cat and Mouse can jump less than the maximum length.<\/li>
Staying in the same position is allowed.<\/li>
Mouse can jump over Cat.<\/li><\/ul>\n\n\n\n
The game can end in 4 ways:<\/p>\n\n\n\n
If Cat occupies the same position as Mouse, Cat wins.<\/li>
If Cat reaches the food first, Cat wins.<\/li>
If Mouse reaches the food first, Mouse wins.<\/li>
If Mouse cannot get to the food within 1000 turns, Cat wins.<\/li><\/ul>\n\n\n\n
Given a rows x cols<\/code> matrix grid<\/code> and two integers catJump<\/code> and mouseJump<\/code>, return true<\/code> if Mouse can win the game if both Cat and Mouse play optimally, otherwise return <\/em>false<\/code>.<\/p>\n\n\n\n
Example 1:<\/strong><\/p>\n\n\n\n<\/figure>\n\n\n\n
Input:<\/strong> grid = [\"####F\",\"#C...\",\"M....\"], catJump = 1, mouseJump = 2\nOutput:<\/strong> true\nExplanation:<\/strong> Cat cannot catch Mouse on its turn nor can it get the food before Mouse.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n<\/figure>\n\n\n\n
Time complexity: O(m^3 * n^3 * max(n, m)) Space complexity: O(m^3 * n^3) <\/p>\n\n\n\n
state: [mouse_pos, cat_pos, turn]<\/p>\n\n\n\n
\n
C++<\/h2>\n
\n\n
\n\/\/ Author: Huahua\nclass Solution {\npublic:\n bool canMouseWin(vector& grid, int catJump, int mouseJump) { \n const int m = grid.size(), n = grid[0].size(); \n int mouse, cat, food;\n for (int pos = 0; pos < m * n; ++pos) \n switch (grid[pos \/ n][ pos % n]) {\n case 'M': mouse = pos; break;\n case 'C': cat = pos; break;\n case 'F': food = pos; break;\n default: break;\n }\n \n const vector> dirs{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};\n const int limit = m * n * 2;\n vector>> seen(m*n, \n vector>(m*n, vector(limit + 1, -1)));\n function dfs = \n [&](int mouse, int cat, int d) -> bool {\n const bool isCat = d & 1;\n if (cat == food || cat == mouse || d >= limit) return isCat;\n if (mouse == food) return !isCat;\n int& ans = seen[mouse][cat][d];\n if (ans != -1) return ans;\n const int cur = isCat ? cat : mouse;\n const int jumps = isCat ? catJump : mouseJump;\n for (const auto& [dx, dy] : dirs)\n for (int j = 0; j <= jumps; ++j) {\n const int x = (cur % n) + dx * j;\n const int y = (cur \/ n) + dy * j;\n const int pos = y * n + x;\n if (x < 0 || x >= n || y < 0 || y >= m || grid[y][x] == '#') break; \n if (!dfs(isCat ? mouse : pos, isCat ? pos : cat, d + 1)) return ans = true; \n }\n return ans = false;\n };\n return dfs(mouse, cat, 0);\n }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
A game is played by a cat and a mouse named Cat and Mouse. The environment is represented by a grid of size rows x cols, where each…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,688,25,689],"class_list":["post-7994","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-memorization","tag-min-max","tag-top-down","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7994","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7994"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7994\/revisions"}],"predecessor-version":[{"id":7996,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7994\/revisions\/7996"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7994"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7994"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7994"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"\"\/](\"https:\/\/assets.leetcode.com\/uploads\/2020\/09\/12\/sample_111_1955.png\")
<\/figure>\n\n\n\n![\"\"\/](\"https:\/\/assets.leetcode.com\/uploads\/2020\/09\/12\/sample_2_1955.png\")
<\/figure>\n\n\n\n