Solutions of Minesweeper - MarisaOJ: Marisa Online Judge

Solutions of Minesweeper

Select solution language

Write solution here.


marcus06    Created at    24 likes

Ở 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(); }