Dò mìn

Điểm số: 1

Giới hạn thời gian: 1s

Giới hạn bộ nhớ: 512 MB

Người đăng: admin

Dò mìn hay gỡ mìn là một trò chơi trên máy tính dành cho một người chơi. Trò chơi được xây dựng như một chương trình giải trí cài đặt trên hệ điều hành Microsoft Windows.

/Users/admin/Pictures/domin.png

Cách chơi:

  • Người chơi khởi đầu với một bảng ô vuông trống thể hiện "bãi mìn".
  • Click chuột vào một ô vuông trong bảng. Nếu không may trúng phải ô có mìn thì kết thúc. Nếu xung quanh ô đó không có mìn thì một vùng các ô sẽ được mở ra cùng với những con số. Số trên một ô là chỉ số ô có mìn trong 8 ô nằm lân cận với ô đó.
  • Nếu  chắc chắn một ô có mìn, người chơi đánh dấu vào ô đó bằng hình lá cờ (click chuột phải).

Để làm ra trò này, người ta dùng 1 ma trận lưu trữ các số. Nếu ô đó là số 0 nghĩa là xung quanh ô đó không có mìn, các số từ 1 đến 8 nghĩa là xung quanh ô đó có số lượng mìn tương ứng, số 9 nghĩa là ô đó là mìn. Một bước quan trọng là khi mở vào ô không có mìn, cũng không phải số, thì toàn bộ các ô không phải mìn xung quanh nó đều được mở ra (như hình trên). Nhiệm vụ của bạn là đếm số lượng ô trống (ô có số 0 là ô trống) được mở ra khi click vào một ô bất kỳ.

Input:

  • Dòng đầu tiên chứa 2 số nguyên n và k; n là kích thước ma trận vuông cạnh n tương ứng với game và k là số lượng lượt click chuột (mở ô).
  • N dòng tiếp theo mỗi dòng gồm n số cách nhau bởi dấu cách.
  • K dòng tiếp theo, mỗi dòng gồm 2 số cách nhau bởi dấu cách là toạ độ của ô được click vào.

Output: k dòng, mỗi dòng gồm 1 số duy nhất là số lượng ô được mở khi click ô tương ứng. Lưu ý nếu ô đã được mở bởi lần click trước đó thì không có ô nào được mở nữa và chỉ đếm những ô trống (ô số 0).

Ví dụ:

Input

Output

5 3

9 1 0 2 9

2 2 1 3 9

0 1 9 2 1

0 1 1 2 1

0 0 0 1 9

3 1

1 2

4 1

5

0

0

Giải thích: Lần mở đầu tiên ở ô (3,1) thì 5 ô không có mìn (ô số 0) lân cận được mở ra. Lần mở thứ 2 là ô (1, 2) thì ô đó mở ra với số 1 nhưng không tính vì chỉ đếm các ô trống mở ra. Lần 3 mở ô (4,1), ô này là số 0 nhưng đã được mở ở lần đầu tiên rồi nên cũng không có ô nào được mở.