Bạn sẽ chơi trò dò mìn trên một bảng gồm \(n\) hàng và \(m\) cột. Mỗi bảng có đúng \(k\) ô chứa mìn, nhưng bạn không biết vị trí của chúng.

Bạn có thể mở một ô để nhận thông tin về ô đó:

• Nếu ô chứa mìn, thao tác trả về -1 và số lần trúng mìn của ván tăng thêm \(1\).
• Nếu ô không chứa mìn, thao tác trả về số ô chứa mìn trong tối đa \(8\) ô kề cạnh hoặc kề góc với nó.

Mục tiêu là mở tất cả các ô không chứa mìn và hạn chế số lần mở trúng mìn. Bạn không cần mở những ô mà mình đã suy ra là có mìn.

Giao diện thư viện

Đây là bài toán sử dụng giao diện hàm. Thí sinh phải thêm dòng sau vào đầu chương trình:

#include "minesweeper.h"

Không viết hàm main. Hãy cài đặt hàm:

void solve(int n, int m, int k, int b, int l);

Máy chấm gọi solve một lần cho mỗi bảng. Các lời gọi diễn ra liên tiếp trong cùng một tiến trình, vì vậy chương trình phải khởi tạo lại trạng thái riêng của từng ván ở đầu hàm. Trong hàm này, bạn có thể gọi:

int open(int x, int y);

Trong đó \((x,y)\) là ô ở hàng \(x\), cột \(y\), được đánh số từ \(0\):

Mỗi lần gọi open trên một ô có mìn đều được tính là một lần trúng mìn, kể cả khi ô đó đã được mở trước đó. Khi solve kết thúc, mọi ô không chứa mìn phải từng được mở ít nhất một lần; nếu không, kết quả của ván không hợp lệ.

Bạn có thể tải mã nguồn mẫu để xem cấu trúc chương trình cần nộp.

Chấm điểm

Mỗi tệp chấm chứa \(10\) bảng có cùng các tham số \(n,m,k,b,l\). Gọi \(p\) là số lần trúng mìn lớn nhất trong \(10\) ván của tệp đó.

• Nếu \(p \le b\), bạn nhận toàn bộ điểm của tệp.
• Nếu \(b < p \le l\), bạn nhận tỉ lệ

điểm của tệp.

• Nếu \(p>l\) hoặc còn ô không chứa mìn chưa được mở, bạn không nhận điểm của tệp.

Bộ dữ liệu gồm ba nhóm:

Mỗi nhóm lần lượt gồm \(27\), \(35\) và \(38\) tệp chấm; mỗi tệp chứa \(10\) bảng cố định.