#include #include #include #include #include using namespace std;

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

struct Cell { int x, y; };

int r, c; vector board; vector<vector> minesAdjacent; vector<vector> flagged; vector<vector> cleared;

void calculateMinesAdjacent() { minesAdjacent.assign(r, vector(c, 0)); for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { if (board[i][j] == 'M') { for (int k = 0; k < 8; ++k) { int ni = i + dx[k]; int nj = j + dy[k]; if (ni >= 0 && ni < r && nj >= 0 && nj < c) { minesAdjacent[ni][nj]++; } } } } } }

int simulate(int startX, int startY) { flagged.assign(r, vector(c, false)); cleared.assign(r, vector(c, false)); cleared[startX][startY] = true; queue q; q.push({startX, startY}); while (!q.empty()) { Cell current = q.front(); q.pop(); int x = current.x; int y = current.y; int f = 0, cov = 0; for (int k = 0; k < 8; ++k) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx >= 0 && nx < r && ny >= 0 && ny < c) { if (flagged[nx][ny]) f++; if (!cleared[nx][ny] && !flagged[nx][ny] && board[nx][ny] != 'M') cov++; } } int m = minesAdjacent[x][y]; if (f == m) { for (int k = 0; k < 8; ++k) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx >= 0 && nx < r && ny >= 0 && ny < c && !cleared[nx][ny] && !flagged[nx][ny]) { if (board[nx][ny] == 'M') return INT_MAX; cleared[nx][ny] = true; q.push({nx, ny}); } } } if (f + cov == m) { for (int k = 0; k < 8; ++k) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx >= 0 && nx < r && ny >= 0 && ny < c && !cleared[nx][ny] && !flagged[nx][ny]) { flagged[nx][ny] = true; } } } } int remaining = 0; for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { if (!cleared[i][j] && !flagged[i][j] && board[i][j] != 'M') { remaining++; } } } return remaining; }

int main() { while (cin >> r >> c && (r != 0 || c != 0)) { board.resize(r); for (int i = 0; i < r; ++i) { cin >> board[i]; } calculateMinesAdjacent(); int minRemaining = INT_MAX; for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { if (board[i][j] != 'M') { int remaining = simulate(i, j); if (remaining < minRemaining) { minRemaining = remaining; } } } } cout << minRemaining << endl; } return 0; }