Minesweeper

529. Minesweeper

class Solution {
    int xx[8]{-1, 0, 1, 1, 1, 0, -1, -1};
    int yy[8]{-1, -1, -1, 0, 1, 1, 1, 0};
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        if (board[click[0]][click[1]] == 'M') {
            board[click[0]][click[1]] = 'X';
            return board;
        }
        
        int h = board.size(), w = board[0].size();
        board[click[0]][click[1]] = 'B';
        queue<int> q;
        q.push(click[0]<<8 | click[1]);

        while (!q.empty()) {
            int y = q.front() >> 8;
            int x = q.front() & 0xff;
            q.pop();
            for (int i = 0; i < 8 ; ++i) {
                int ny = y + yy[i], nx = x + xx[i];
                if (0 <= ny && 0 <= nx && ny < h && nx < w) {
                    if (board[ny][nx] == 'M') {
                        if (board[y][x] == 'B') {
                            board[y][x] = '1';
                        } else {
                            board[y][x]++;
                        }
                    }
                }
            }
            if (board[y][x] == 'B') {
                for (int i = 0;i < 8 ; ++i) {
                    int ny = y + yy[i], nx = x + xx[i];
                    if (0 <= ny && 0 <= nx && ny < h && nx < w) {
                        if (board[ny][nx] == 'E') {
                            board[ny][nx] = 'B';
                            q.push(ny << 8 | nx);
                        }
                    }
                }
            }
            cout<<endl;
        }
        return board;
    }
};

클릭한 곳이 지뢰면, 좌표 값을 X 로 변경하고 리턴.

클릭한곳이 E 면, B 로 바꾸고 좌표를 큐에 넣는다.
현재 좌표의 팔방을 탐색하며 지뢰가 있으면 현재 좌표에 카운트를 늘린다.
현재 좌표가 여전히 B 이면 팔방 중 E 인 좌표를 큐에 넣고 큐에 넣은 좌표의 값은 B 로 바꿔서 visit 표시 한다.
큐가 빌때까지 반복.

Time: O(n^2)

• 모든 보드를 탐색하게 되므로 n^2

Space: O(n)

• queue 최대 값 n