TRÒ CHƠI Ô CHỮ Một ô chữ được mô tả là một hình chữ nhật gồm ???? dòng, ???? cột. Một vài ô tự do và một số ô bị khóa. Biết rằng một từ được điền vào ô ch

TRÒ CHƠI Ô CHỮ
Một ô chữ được mô tả là một hình chữ nhật gồm ???? dòng, ???? cột. Một vài ô tự do và một số ô
bị khóa. Biết rằng một từ được điền vào ô chữ phải điền theo quy tắc sau:
Bước 1:
• Độ dài của một từ ít nhất là 3 kí tự (tức là cần tối thiểu 3 ô liên tiếp để điền được 1 từ)
– 3 ô này phải là ô tự do.
• Phải xác định được ô đầu của một từ (có thể theo chiều ngang hay dọc). Nếu một từ
điền theo chiều ngang thì ô đầu tiên của một từ hoặc là ô trái nhất của 1 hàng hoặc ô
bên trái của ô đó là một ô bị khóa. Nếu điền theo chiều dọc của ô chữ thì ô đầu của một
từ hoặc là ô đầu của một cột hoặc ô phía trên của ô đó là một ô bị khóa.
-3 -2 -1 0 1 2 3 4 5
Bước 2: Ta gán 1 cho mỗi ô là ô bắt đầu của một từ một số nguyên. Các ô này được gán các số
lần lượt bắt đầu từ 1 theo đúng trình tự: các ô được đọc lần lượt theo hàng: hàng 1, hàng 2,..
trên mỗi hàng lại đọc từ trái qua phải.. Chỉ các ô bắt đầu của một từ mới được đánh số.
Ví dụ: Quy ước tại 1 ô chứa dấu “.” là ô tự do, ô chứa “#” là ô bị khóa, nếu cho mô tả của một
ô chữ như sau:
…
#..
…
..#
.##
Khi đó, ở các ô chứa dấu “!” là ô có thể bắt đầu 1 từ:
!!!
#..
!..
..#
.##
Ta lần lượt đánh số các ô này theo quy ước ở bước 2:
123
#..
4..
..#
.##
Ở hàng thứ 2 không có từ nào cả vì độ dài không thỏa mãn.
Yêu cầu: Cho một mô tả ban đầu về ô chữ, hãy cho biết ô chữ đố có bao nhiêu từ và vị trí các
ô là ô đầu của mỗi từ theo mô tả ở trên
Dữ liệu: vào từ ile văn bản CROSSWORDS.INP
• Dòng đầu gồm 2 số n và m (????, ???? ≤ 50).
• ???? dòng tiếp theo, mỗi dòng gồm ???? kí tự “.” hoặc “#” mô tả ô ở vị trí tương ứng là ô tự
do hay ô bị khóa.
Kết quả: Ghi ra file văn bản CROSSWORD.OUT:
• Dòng đầu là số lượng các từ có thể của ô chữ.
• Mỗi dòng tiếp theo ghi 2 số là chỉ số hàng và cột của ô đầu của mỗi từ theo quy tắc
điền từ ở trên.