{"id":6447,"date":"2020-03-09T20:18:39","date_gmt":"2020-03-10T03:18:39","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6447"},"modified":"2020-03-09T20:31:55","modified_gmt":"2020-03-10T03:31:55","slug":"leetcode-529-minesweeper","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-529-minesweeper\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 529. Minesweeper"},"content":{"rendered":"\n

Let’s play the minesweeper game (Wikipedia<\/a>, online game<\/a>)!<\/p>\n\n\n\n

You are given a 2D char matrix representing the game board. ‘M’<\/strong> represents an unrevealed<\/strong> mine, ‘E’<\/strong> represents an unrevealed<\/strong> empty square, ‘B’<\/strong> represents a revealed<\/strong> blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit<\/strong> (‘1’ to ‘8’) represents how many mines are adjacent to this revealed<\/strong> square, and finally ‘X’<\/strong> represents a revealed<\/strong> mine.<\/p>\n\n\n\n

Now given the next click position (row and column indices) among all the unrevealed<\/strong> squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:<\/p>\n\n\n\n

  1. If a mine (‘M’) is revealed, then the game is over – change it to ‘X’<\/strong>.<\/li>
  2. If an empty square (‘E’) with no adjacent mines<\/strong> is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed<\/strong> squares should be revealed recursively.<\/li>
  3. If an empty square (‘E’) with at least one adjacent mine<\/strong> is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.<\/li>
  4. Return the board when no more squares will be revealed.<\/li><\/ol>\n\n\n\n

    Example 1:<\/strong><\/p>\n\n\n\n

    Input:<\/strong> \n\n[['E', 'E', 'E', 'E', 'E'],\n ['E', 'E', 'M', 'E', 'E'],\n ['E', 'E', 'E', 'E', 'E'],\n ['E', 'E', 'E', 'E', 'E']]\n\nClick : [3,0]\n\nOutput:<\/strong> \n\n[['B', '1', 'E', '1', 'B'],\n ['B', '1', 'M', '1', 'B'],\n ['B', '1', '1', '1', 'B'],\n ['B', 'B', 'B', 'B', 'B']]\n\nExplanation:<\/strong>\n\n<\/pre>\n\n\n\n
    Example 2:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> \n\n[['B', '1', 'E', '1', 'B'],\n ['B', '1', 'M', '1', 'B'],\n ['B', '1', '1', '1', 'B'],\n ['B', 'B', 'B', 'B', 'B']]\n\nClick : [1,2]\n\nOutput:<\/strong> \n\n[['B', '1', 'E', '1', 'B'],\n ['B', '1', 'X', '1', 'B'],\n ['B', '1', '1', '1', 'B'],\n ['B', 'B', 'B', 'B', 'B']]\n\nExplanation:<\/strong>\n\n<\/pre>\n\n\n\n
    Note:<\/strong><\/p>\n\n\n\n
    1. The range of the input matrix’s height and width is [1,50].<\/li>
    2. The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.<\/li>
    3. The input board won’t be a stage when game is over (some mines have been revealed).<\/li>
    4. For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t<\/strong> need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.<\/li><\/ol>\n\n\n\n
      Solution: DFS<\/strong><\/h2>\n\n\n\n
      Time complexity: O(m*n)
      Space complexity: O(m* n)<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector> updateBoard(vector>& board, vector& click) {\n    const int m = board.size();\n    const int n = board[0].size();\n    function dfs = [&](int x, int y) {\n      if (board[y][x] != 'E') return;\n      int c = 0;\n      for (int tx = x - 1; tx <= x + 1; ++tx)\n        for (int ty = y - 1; ty <= y + 1; ++ty)\n          if (tx >= 0 && tx < n && ty >= 0 && ty < m)\n            c += board[ty][tx] == 'M';\n      \n      if (c > 0) {\n        board[y][x] = '0' + c;\n        return;      \n      }\n      \n      board[y][x] = 'B';      \n      \n      for (int tx = x - 1; tx <= x + 1; ++tx)\n        for (int ty = y - 1; ty <= y + 1; ++ty)\n          if (tx >= 0 && tx < n && ty >= 0 && ty < m)\n            dfs(tx, ty);\n    };\n    int x = click[1];\n    int y = click[0];\n    dfs(x, y);\n    if (board[y][x] == 'M') board[y][x] = 'X';\n    return board;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
      Solution 2: BFS<\/strong><\/h2>\n\n\n\n
      \n
      Python3<\/h2>\n
      \n\n
      \n# Author: Huahua\nclass Solution:\n  def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n    m, n = len(board), len(board[0])\n    cx, cy = click[1], click[0] \n    q = [(cx, cy)]\n    while q:\n      q2 = []\n      for x, y in q:        \n        if board[y][x] != 'E': continue\n        c = 0\n        for tx in range(x - 1, x + 2):\n          for ty in range(y - 1, y + 2):\n            if 0 <= tx < n and 0 <= ty < m and board[ty][tx] == 'M':\n              c += 1\n        if c > 0:\n          board[y][x] = chr(ord('0') + c)\n          continue\n        board[y][x] = 'B'\n        for tx in range(x - 1, x + 2):\n          for ty in range(y - 1, y + 2):\n            if 0 <= tx < n and 0 <= ty < m and board[ty][tx] == 'E':\n              q2.append((tx, ty))              \n      q = q2\n    if board[cy][cx] == 'M': board[y][x] = 'X'\n    return board\n<\/pre>\n<\/div><\/div>\n\n\n\n
      <\/p>\n","protected":false},"excerpt":{"rendered":"
      Let’s play the minesweeper game (Wikipedia, online game)! You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[33,278,177],"class_list":["post-6447","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dfs","tag-grid","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6447","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=6447"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6447\/revisions"}],"predecessor-version":[{"id":6449,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6447\/revisions\/6449"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6447"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6447"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6447"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}