Ở mỗi ô ta có 2 trạng thái là đặt bomb hoặc không đặt bomb. Ta sẽ thử hết tất cả các trường hợp có thể xảy ra với độ phức tạp n x m x 2^(n x m).

Để tối ưu hơn, ta áp dụng kĩ thuật nhánh và cận. Ở đây mình đệ quy theo thứ tự từ trái sang phải và từ trên xuống dưới cho dễ làm. Ở ô (i, j), ta sẽ kiểm tra các ô (0, 1, …, m-1) của hàng (i - 2) xem có thỏa mãn input đề bài hay không. Tiếp đến, ta sẽ kiểm tra các ô (0, 1, …, j - 2) của hàng (i - 1) xem có thỏa mãn input đề bài hay không. Ở đây hàm count(x, y) dùng để đếm số bom xung quanh ô (x, y)

#include <bits/stdc++.h>
using namespace std;

const int N = 25;

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

int n, m;
int a[N][N], grid[N][N];

int count(int x, int y) {
    int res = 0;
    for (int i = 0; i < 8; ++i) {
        int u = x + dx[i], v = y + dy[i];
        if (u >= 0 && v >= 0 && u < n && v < m) {
            res += grid[u][v];
        }
    }

    return res;
}


bool notPossible(int i, int j) {
    if (i > 1) {
        for (int y = 0; y < m; ++y) {
            if (count(i - 2, y) != a[i - 2][y]) return true;
        }
    }

    if (i > 0) {
        for (int y = 0; y + 1 < j; ++y) {
            if (count(i - 1, y) != a[i - 1][y]) return true;
        }
    }

    return false;
}

void print_grid() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << grid[i][j] << ' ';
        }
        cout << '\n';
    }
}

bool dfs(int i, int j) {
    if (i == n) {
        for (int x = 0; x < n; ++x) {
            for (int y = 0; y < m; ++y) {
                if (count(x, y) != a[x][y]) return false;
            }
        }
        return true;
    }

    if (notPossible(i, j)) return false;

    int u = i + (j + 1) / m, v = (j + 1) % m;

    for (int k = 1; k >= 0; --k) {
        grid[i][j] = k;
        if (dfs(u, v)) return true;
    }
    
    return false;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }

    if (dfs(0, 0)) print_grid();
}