TAMCAM - Tam Cam

no tags 

Năm nào cũng vậy, khi mọi người nô nức rủ nhau đi chơi xuân cũng là lúc mẹ con Cám ngồi bày mưu tính kế để bắt Tấm phải ở nhà. Lần này Cám lấy những hạt thóc và hạt gạo đặt vào các ô của một bảng ô vuông kích thước m×n, mỗi ô đặt tối đa một hạt. Xong đâu đấy Cám gọi Tấm ra yêu cầu phải nhặt ra khỏi bảng một số ít nhất các hạt sao cho trên mỗi hàng cũng như trên mỗi cột của bảng còn lại, số hạt thóc bằng số hạt gạo, khi nào làm xong và đúng mới được đi chơi. Sau một hồi loay hoay không làm được, Tấm òa khóc nức nở, Bụt hiện lên hỏi “Vì sao con khóc?”…

Sau khi nghe Tấm kể lại sự tình, Bụt nói: “lần này mẹ con nó chơi khó thế thì ta cũng đành bó tay thôi, nhưng mà ta còn một cách: con gửi cái bảng này lên trang VNOI.INFO, thế nào cũng có người giúp con”. Nói xong Bụt biến mất.

Câu chuyện tiếp theo như thế nào các bạn làm xong sẽ biết…

Dữ liệu

  • Dòng 1 chứa hai số nguyên dương m,n≤100 cách nhau đúng một dấu cách.
  • m dòng tiếp theo, dòng thứ i chứa n ký tự liền nhau, ký tự thứ j là “G”, “T”, hoặc “.” (dấu chấm), cho biết ô (i,j) chứa hạt gạo, hạt thóc, hay là ô trống.

Kết quả

  • Dòng 1 ghi số hạt ít nhất phải nhặt ra khỏi bảng.
  • m dòng tiếp theo, dòng thứ i ghi n ký tự liền nhau, ký tự thứ j là “G”, “T”, hoặc “.” (dấu chấm), cho biết ô (i,j) còn lại hạt gạo, hạt thóc, hay là ô trống.

Chú ý: Các hàng ô của bảng được đánh số từ 1 tới m theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số từ 1 tới n theo thứ tự từ trái qua phải. Ô nằm ở hàng i, cột j của bảng gọi là ô (i,j).

Ví dụ

Dữ liệu
4 5
GT.GG
GGTGT
TTGTG
GTGT.	

Kết quả
6
.T.G.
.GTGT
T.GTG
G..T.



Added by:Jimmy
Date:2009-02-04
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:VNOI Marathon 2009
Round 1
Problem Setter: Lê Minh Hoàng