VM 14 Bài 04 - Đếm hình chữ nhật

Xem dạng PDF

Gửi bài giải

Điểm: 1,23 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Nguồn bài:
VM14 - RR
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bạn được cho một bảng hình chữ nhật kích thước ~R \times C~:

  • Trên bảng có một số khung hình chữ nhật rỗng (chỉ gồm 4 cạnh của hình chữ nhật).
  • Các khung hình chữ nhật có thể lồng nhau, nhưng không có 2 khung hình chữ nhật nào chạm nhau (nghĩa là không có ô nào của bảng thuộc nhiều hơn 1 khung hình chữ nhật, và không có 2 ô chung cạnh hay chung đỉnh thuộc 2 khung hình chữ nhật khác nhau). Nói cách khác, hai hình chữ nhật lồng nhau có nghĩa là một hình chữ nhật này nằm hoàn toàn bên trong một hình chữ nhật kia.
  • Mỗi ô trên bảng là 'o' hoặc '.'. Ký tự 'o' thể hiện ô đó thuộc một khung hình chữ nhật và ký tự '.' thể hiện ô đó không thuộc bất kỳ khung hình chữ nhật nào.

Bạn cần tìm dãy dài nhất các hình chữ nhật ~A_1, \dots, A_k~ mà ~A_1~ nằm trong ~A_2~, ~A_2~ nằm trong ~A_3~, ...~A_i~ nằm trong ~A_{i + 1}~, ...~A_{k - 1}~ nằm trong ~A_k~.

Input

Dòng 1: số nguyên dương ~T~ - số lượng test ~(T \le 2)~.

Tiếp theo là ~T~ test, mỗi test gồm:

  • Dòng đầu: 2 số nguyên dương ~R~ và ~C~ ~(1 \le R, C \le 2000)~.
  • Tiếp theo là R dòng, mỗi dòng gồm ~C~ ký tự. Mỗi ký tự là 'o' hoặc '.'

Tất cả các hình chữ nhật đều hợp lệ và có cạnh lớn hơn hoặc bằng 3.

Output

Gồm ~T~ dòng, mỗi dòng một số nguyên duy nhất là kết quả của bài toán

Sample Input 1

1
5 5
.....
.....
.....
.....
.....

Sample Output 1

0

Sample Input 2

1
11 11
ooooooooooo
o.........o
o.ooooooo.o
o.o.....o.o
o.o.ooo.o.o
o.o.o.o.o.o
o.o.ooo.o.o
o.o.....o.o
o.ooooooo.o
o.........o
ooooooooooo

Sample Output 2

3

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.