Fork me on GitHub

Minesweeper

Posted on

Description

https://leetcode.com/problems/minesweeper/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int rowSize = board.size();
        int columnSize = board[0].size();
        int row = click[0]; 
        int column = click[1];
        vector<vector<bool>> visited(rowSize, vector<bool>(columnSize, false));
        if (board[row][column] == 'M') {
            board[row][column] = 'X';
            return board;
        }
        vector<pair<int, int>> directions = {
            {-1,-1}, {1, 1}, 
            {1, 0}, {-1, 0}, 
            {0, -1}, {0, 1},
            {-1, 1}, {1, -1}
        };
        
        helper(board, row, column, directions, 
                        rowSize, columnSize, visited);
        return board;
    }
    
    void helper(vector<vector<char>>& board, int curRow, 
            int curColumn, vector<pair<int, int>>& directions,
                int rowSize, int columnSize, vector<vector<bool>>& visited) {
        if (visited[curRow][curColumn]) return;
        visited[curRow][curColumn] = true;
        if (board[curRow][curColumn] == 'M') {
            board[curRow][curColumn] == 'X';
            return;
        }
        int count = 0;
        vector<pair<int, int>> adjacents;
        for (auto& item : directions) {
            int newRow = item.first + curRow;
            int newColumn = item.second + curColumn;
            if (newRow < 0 || newRow >= rowSize || 
                newColumn < 0 || newColumn > columnSize) continue;
            if(board[newRow][newColumn] == 'M' || board[newRow][newColumn] == 'X') {
                count += 1;
            }
            if(board[newRow][newColumn] == 'E' && !visited[newRow][newColumn]) {
                adjacents.push_back(make_pair(newRow, newColumn));
            }
        }
        if (count == 0) {
            for (auto& item : adjacents) {
                helper(board, item.first, item.second, 
                       directions, rowSize, columnSize, visited);   
            }
        }
        board[curRow][curColumn] = count ? count + '0' : 'B';
    }
};