Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CMOUSE - Bắt chuột

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/cmouse


Một ngày nọ, Tí Chuột tìm đường về hang của mình. Hang của Tí Chuột có rất nhiều cửa hang nằm rải rác trên các ô của một bảng hình chữ nhật kích thước M x N. Chỉ cần đi vào bất kỳ cửa hang nào là Tí Chuột sẽ về được chỗ ở của mình. Trên một số ô có vật cản và Tí Chuột không thể đi vào các ô đó. Mỗi bước Tí Chuột có thể đứng nguyên tại chỗ hoặc đi vào một trong 4 ô kề cạnh xung quanh. Tí Chuột rất thông minh, do đó nó luôn chọn đi theo ô nằm trong đường đi ngắn nhất để về hang. Nếu có nhiều lựa chọn, Tí Chuột sẽ ưu tiên theo thứ tự: đi lên trên, đi sang phải, đi xuống dưới, đi sang trái và đứng yên.

Tuy nhiên Bé Mèo không muốn Tí Chuột về được hang của mình. Bé Mèo cũng thông minh không kém; mỗi bước Bé Mèo sẽ tìm cách đặt một vật cản vào một ô trống, và tất nhiên phải là ô Tí Chuột không đang đứng. Mục tiêu của Bé Mèo là tìm cách đặt vật cản sao cho Tí Chuột không còn đường về hang nữa.

Bạn hãy lập trình giúp Bé Mèo đặt càng ít vật cản càng tốt để đạt được mục tiêu nhé! Biết rằng ở bước đi đầu tiên, Bé Mèo sẽ đặt vật cản trước, sau đó mới đến lượt Tí Chuột đi.

Input

Dòng đầu tiên chứa 2 số nguyên M và N (1 <= M, N <= 12).

M dòng tiếp theo, mỗi dòng chứa N ký tự mô tả bảng hình chữ nhật, trong đó ký tự '.' mô tả ô trống, ký tự 'O' mô tả một miệng hang, ký tự '#' mô tả vật cản và ký tự '*' mô tả vị trí ban đầu của Tí Chuột. Dữ liệu đảm bảo luôn có đúng một ký tự '*'.

Output

Dòng đầu tiên in ra số nguyên K là số vật cản Bé Mèo sẽ đặt. K dòng tiếp theo mỗi dòng chứa 2 số x, y là tọa độ dòng, cột của một vật cản Bé Mèo cần đặt. Các dòng của bảng được đánh số 1..M từ trên xuống, các cột được đánh số 1..N từ trái sang.

Điểm

K càng thấp bạn càng được điểm cao. Nếu cách đặt vật cản không hợp lệ hoặc sau khi đặt các vật cản Tí Chuột vẫn còn đường vào hang, bạn sẽ không nhận được điểm cho test tương ứng.

Example

Input:
3 3
..O
...
*..

Output:
3
2 2
1 1
3 2

Giải thích

Đầu tiên Bé Mèo đặt vật cản tại ô (2,2), Tí Chuột có thể đi sang ô (2,1) hoặc (3,2), tuy nhiên do Tí Chuột ưu tiên đi lên trên nên nó sẽ đi lên ô (2,1). Bé Mèo lại đặt vật cản tại ô (1,1), Tí Chuột phải quay về ô (3,1); Bé Mèo đặt vật cản tại ô (3,2) và thắng cuộc.


Được gửi lên bởi:Jimmy
Ngày:2010-06-29
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:VM10 - Tác giả: Ngô Minh Đức

hide comments
2013-06-28 08:23:27 anh chỉ ju vài em......!!!!!!!!!!!
z MEO bat dau dj tu dau z?
2011-12-12 07:39:37 Bui Duy Thong
bài này k càng nhỏ càng tốt.điểm càng cao.ko nhất thiết phải là k min
2011-05-08 00:08:41 ☺Minh Thach☼
de thi hoc sinh gioi tinh binh dinh 2011. Gap lai ma muon rot nuoc mat.
2010-11-12 09:07:40 Ðinh Quốc Toàn
sao ko đặt ở ô 2 1 và 3 2 thế là khỏi về lun??? giải thích nghe tý coi!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.