[codeSignel] Minesweeper

In the popular Minesweeper game you have a board with some mines and those cells that don't contain a mine have a number in it that indicates the total number of mines in the neighboring cells. Starting off with some arrangement of mines we want to create a Minesweeper game setup.

Example

For

matrix = [[true, false, false], [false, true, false], [false, false, false]]

the output should be

mi!nesweeper(matrix) = [[1, 2, 1],

                               [2, 1, 1],

                               [1, 1, 1]]

 

이 문제는 지뢰찾기 문제다.

간단히 설명해서 좌,우 상,하, 대각선에 걸린 모든 true를 세면 되는 비교적 간단한 문제다.

int dx[8] = {1,-1,0,0, -1, 1, -1, 1};
int dy[8] = {0,0,-1,1, 1, 1, -1, -1};

int switching(vector<vector<bool>> matrix ,int x,int y) {
    int count = 0;
    for(int i = 0; i<8;i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || matrix.size() <= nx || ny < 0 || matrix[0].size() <= ny) continue;
        if (matrix[nx][ny]) count++;
    }
    return count;
}

vector<vector<int>> minesweeper(vector<vector<bool>> matrix) {
    vector<vector<int>> con(matrix.size(),vector<int>(matrix[0].size()));
    
    for(int i = 0; i<matrix.size();i++) {
        for(int j = 0; j<matrix[0].size();j++) {
          con[i][j] = switching(matrix, i,j);    
        }
    }
        
    return con;
}

 

이 문제에서는 방향 벡터를 이용해서 문제를 해결하였다.

1 과 -1의 조합으로 대각선에 걸린 true를 셀수 있다.

이 문제는 다른 문제들과 비교했을때 간단한게

자기 자신만 비교하면 된다. 그러니까 끝까지 갈 필요가 없다는 이야기다.

여기에서도 범위가 벗어나면 안되기 때문에 예외 처리를 해두었다.

std::vector<std::vector<int>> minesweeper(std::vector<std::vector<bool>> grid) {
    int n = grid.size();
    int m = grid[0].size();
    int fx[] = {-1,-1,-1,0,1,1,1,0};
    int fy[] = {-1,0,1,1,1,0,-1,-1};
    vector<vector<int> > ret(n, vector<int>(m, 0));
    for(int i = 0; i<n; i++)
        for(int j = 0; j<m; j++)
        {
            int sum = 0;
            for(int k = 0; k<8; k++)
            {
                int x = i + fx[k];
                int y = j + fy[k];
                if(x < n && x > -1 && y < m && y > -1 && grid[x][y]==true) sum++;
            }
            ret[i][j] = sum;
        }
    return ret;
}