Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type

Cho một bảng kí tự kích thước ~M*N~, chỉ gồm hai kí tự `~X~` và `~.~`.

Yêu cầu: Tìm hình chữ nhật có chu vi lớn nhất thỏa mãn:

  • Các cạnh của hình chữ nhật song song với các cạnh của bảng kí tự.
  • Chỉ chứa kí tự `~.~`.
  • Hình chữ nhật có chu vi lớn nhất.

Input

  • Dòng đầu chứa hai số nguyên dương ~M,N (M,N \leq 400)~;
  • Dòng thứ ~i~ trong số ~M~ dòng tiếp theo chứa ~N~ kí tự ~A_{i,1},A_{i,2},\ldots,A_{i,N} (A_{i,j}=~`~X~` hoặc `~.~`~)~

Output

  • In ra duy nhất một số là chu vi hình chữ nhật lớn nhất tìm được.

Example

Sample input 1

2 2
..
..

Sample output 1

8

Sample input 2

4 4
X.XX
X..X
..X.
..XX

Sample output 2

10

Sample input 3

3 3
X.X
.X.
X.X

Sample output 3

4

Be the first to comment

Comments

There are no comments at the moment.