题目描述
A farmer has a rectangular land of size m×n. There are swamps in the land where the fencing is not possible. You need to find the perimeter of the largest rectangular fence that can be built on this land.
Input format:
The first line contains m and n. The next m lines contain n characters each describing the state of the land. 'x' (ascii value: 120) if it is a swamp and '.' ( ascii value:46) otherwise.
Output Format:
Output contains a single integer - the largest perimeter. If the rectangular fence cannot be built, print "impossible" (without quotes).
Constraints:
2≤m,n≤1000
Sample input 1:
2 2
.x
x.
Sample output 1:
impossible
Sample Input 2:
2 5
. . . . .
xxxx.
Sample Output 2:
impossible
Register for Algorithms in IndiaHacks
SAMPLE INPUT
4 5
.....
.x.x.
.....
.....
SAMPLE OUTPUT
14
Explanation
The perimeter is 2∗(4−1)+2∗(5−1)=14.
输入格式
见题面
输出格式
见题面
样例输入
283 37
..x..x....xx....x.xx....xx..x..x.....
x..x.xx..x..x.....xx...xx.x...xx..x..
..x..xx.x..x....xx....x.xx...x..x....
x....xxxx...x.x..x.......xxxx..x..x..
..x.x.x..x..x..x.....x.xx.x...xx..x..
.x..x.x....x..x...xxx....xx..x...x.x.
x....x....x....x..xxxx.......xx.xx.x.
...xx.x....xx...x..x..xx..x.......xxx
.x..x.x..x..x....x.x.x..x.x...x.x...x
.x....xx.x..x..x.......x.....xxx..x.x
xx.....xxx..x...x......xx.x.x.x.x....
xx..x....x..x.xx..x..x....x.x....x...
..xx.xx...xx.x..x.....x....x....xx.x.
x.xxx...x.......x.xxx..x...x...x.xx.x
.x..x..x..x....x.x.x.x..x....xx..x..x
...x.x.x..x....x...x.xx..x....xx.x...
.xx...xx..x...x.x...x..x...x...xxx..x
...x.x....xx.x..x..x.....x....x.xxx..
x.x....xx........xxxx.x..x..x....x...
.xxx.x...x.x...xx..x............xxx..
....xx..x.x...x..x.xx.xx...xxx..x....
..x.....x.xxx..xx..x.xx..x..x..x...x.
..xx...x.x..x.x.....x.x...x..xxx.....
.xxx..x....x...xx.x.x...x.x.x..x..x..
.x.......x..x.x...x.xxxx..x..x..x..x.
.x..x.x..x..x...xx..x...x.x....x..xx.
.x.x...x...xx...xx...x.x..x...x.x...x
.x.x...x.x..x...x.x..x.x...x.x...x...
xx...xx..x..x...x...xx.....xxx....x.x
.x....x.xx..x....x..x.x.x.x..x....xx.
.x..x..x..x.x..x...x.....xx...x.xx..x
.x.....xx.x..x..x....x....xxx...x.x..
.xx.x...x.x..x.x..x.......x.xx.x..x.x
....xx..x.x.......x.xxx..x....x..xx..
.x.......x....xxx.x..x...x...x.......
x........x..x.x.xxx..x.xx......xxxxxx
x.xx....x.x.xx..x..x.....xxx..x...x..
x.x...x......x..xx.x...xx..x.x.x.x..x
...x..x.x...x..x...x..x...xx.x.x.x..x
....x.x.x..x..x..x.x..x...x..x.x..x.x
...x.x..x.....xx..xx..x...x.x..x..x..
....x..xxx...xx...x.x.x....xx..x.....
.x..x...xx.x..x.x....xx.xx..x..x..x..
.x.x..x.x...x...x.x...x..xx...x...x..
......x....xx.x..x.x.xxx..x.xx..x...x
x..x..x..x..x.x...x.x....xx..x.......
xx....x.xx.x.x.....x...x.xx.x.x.x...x
x.....x.xx..x..x...x....x......x.x.xx
xx..x.x..x..x..x..x..x.x.....x.x..xx.
.x..x.x....xx..x.....xx.x.x....xx....
.x..xx..xx..x.....x.xx..x..x..x.x....
xx..x...x..xx...x.x...x...xx....x...x
xx..x...x...xx.x..x..x..x..x...x.x..x
.x..x....x.x.x....x...x...xxx.....xx.
xx.....x..xx.x..x..x.x..x....x..xx...
x..xx..x...x.x...x.x..x.x..x..x..x..x
..x..x...x.x.x..x.....xx..x.x.x..x...
x.....x...xxxx...x.x.....x.x..xx.....
x..xx.x...xx..x..x......x..x..xxx....
xx..xx...x..x..x..x......xx....xx.x.x
..xx.x..x..x..x....xx.x...x..x..x..x.
x.x..x...x..x..x.x...xx..x..x.......x
xx....xx...xx......xx.x.xx..x...x..x.
x..x...xx..x...x.x...x.x.....x.x.xx..
x...x...xx..x...xx.....x..xx.....x.x.
x.x..x..x.x.........xxxxx.x..x..x..x.
....x..xx..x......x.x...x.xx.x..x...x
x..x.x..x..xx...x.x.x...x.x..x..x..x.
..x..xx..x..x.....xx.x.x...x..x..x...
.x..xxx..x...x...x.x...xx.x.....x..x.
xx....xx.x..x..x..x..x....x.........x
xxx.xx.x.....x..x..x..x.xx.x...x...xx
..x..x....x.....xxxx.x..x..x....xx..x
..x.x..x...x.x.....x..xx..x..xx.....x
.xx.x..x..x......x.....xx..x..x.x..xx
x...xx..x..x..x..x..x...x.x...xx.x...
...x.x...x.x..xx.x.....xx.x..xx..x...
x..x..x.x.x..x...x..x......x.xxx.....
..x.xxx.x..x.x..x..x..x..x..x..x...xx
....xx..x......x...xxx.x.....xxx....x
..x.xx..x....xx....xx.x..x..x..x.....
..x..xxxx..x.....xx.x..x.x..x...x...x
x......x..xxx..x...x.x.x.x..x..x..x..
x...x.x...x.x...x.x.x....x.x.x..x....
xx....xx.x.x...x..x..x....xx..x.x....
xx..x.....x.xxx..x...x..x..x..x.x...x
.x......x...x.x.xxx.x..x...x.x......x
...x.x.x...x.xx.....xxx..x....x.x.xx.
..x.x...x...x.x..x.x.x.x....x.x...xx.
.x......xx..x.x.x.x..x..x..x.x..x..x.
.x...x..xx...x.x....x.x..x.x..x...x.x
...xx......xx..xx.x..x...x..x.x......
x..xxx.x..x..x......x.xxx..x...x...x.
xx...x.x....x.x.x.x...x...xx..x....x.
xx..x..x...x.x......xx.x..x....xx...x
x..xx....x..x.x.x..x..x.x..x..x..x...
x....x.x...xxx....x..xx..x.x..x..x...
.xx...x..x..xx......xx.x..x..x..xx..x
..x..x..x....xx.x..x..x..x....x.xx...
.x....xxx..x...xx..x..x..x...x...xx.x
.....x..xx.x..x..x...xx..x...x....x.x
x..x....x..xx.x..x....xx..x.x....xx..
.x..x.x.x..x..x....xx..x.x....x.x....
x..xx.x.......x..x.xx..x..x.xx..x.x..
x..x....x.....xx.xx..x.x..x..x..x..x.
.x..x..x.x......xx.x..x.x.x....xx.x..
...xx..x..x.....x..xxx.x...x...x..x..
xx.x..x....x.x.x....xx..x..x..x..x..x
.x.x..x...x.x...x....x..xx..xx.......
x...x.xx.x.xx..x...x...x............x
xxx.x..x.xx.x..x..x..xx.x...xx.....x.
...xx..xx.x.x..x...x...xx..x...x..xx.
...xx..x..x..x.x....x.x.....xxx..x.x.
...x...x.x.x...xx.x...x.x..x..x....x.
...xxx.x..x..x...x.x....x.xx..x..x..x
..x.x...x....xx.x...x....xx...x....xx
.x.x..xx...x...xx.......xx.xx..x...x.
x...x.x....x..x.xx..x.x..x..x.x..x..x
...x.x.....xx......x.x.x.xx.x..x.x...
.x...xx.x..x..x...xx....x.x..x..x..xx
...x.x....xx..x..x.x......xxx..x.....
.xx.x...x.x.x.x....xx...xx....x.x....
..x..x.xxx.x.......x..x.xx.x..x.x.x..
x......x..xx.xx.........x.x.x....xx.x
x.xx.....xx.x..x..x..x..x.x..x.x..x..
x....xx..x....xx....x.x.x..x.x...x.x.
..xx..x.......x.x.x...xxx.x...x.x...x
.x..x..x..x.x....xx..x.x...x...xx...x
.x.x...x....x..xx.x....xx..x.....xx..
x.x..xx....x.x..x.x..x..x.x...x..x...
.......xxx.x.x.xx.x....xx...xx...x..x
...x..xx.....x..xxx...x.x...x..xx..x.
.x..x..x...x....x.xx..x...x.x.x....xx
..x....x.x....x.xx.x.x...x..x.x......
xx..xx.x....x....x....xx..x..xxx.x...
.xx.x..x...x..x.x..x....xx.x..x.....x
..xx..x.x.x..x..x.....x.x.x..xx....x.
x.x..x...xx..x..x..x....xx..x..x.x...
x.......x.xxx.x..x.x..x....xx...x....
..x.x..x.x.xx.......xx.x....x..x...x.
.x.xx.....xx.x.xxx..x.x....x..x.x.x..
x...xx..x.......x.x......xx..x.....x.
..x.x..x.xx..x.xxxx..x..xx..x..x...x.
..xx....xx....xx.x..x...x...xx.x..x..
x....x...x.xx.....xxx....x....xx..x.x
x.....xx..x.x.x...x.....xx.x....xxx..
..x.x..x.x...x..x...xx.x...x..x......
.x.xxxx...x..x.x..x.x..x..x..x..x....
....x...xxxxx....x..x.x.x.x..x..x...x
.x...x.x..x..x..x.....x.xxx...x.x..x.
..x...xx.x..x.....xx..x.x..x...xx..x.
...xx..x..x...x..xx....x.x.x..x.x....
x.x.x....x.x.x.x...x.x....x.x....xxx.
.x..x..x....xx...xx..x..x...x.x..x...
..xx.x...x.x.x..x..x..x.x....x.x.x...
x....x.xx.x...x.x..x..x.x..x..x....xx
...x.x..x.x...x......xxx.x..x..x...x.
.xx...x.x.x...x.x..x....x......xxx..x
x..x.x...x....xx..x..xx.......x..xx..
xx........x.xx...xx.xxx..x....xx....x
..x.xx...x.x...x.x..x..x.x..x...x..x.
..xx...x.x.x..x...x.x.x..x...x..x.x..
x..x...xx....xx...x....x...x...x.x.x.
..x.xx.xx..x..x...x...x.x.x.x......xx
...x.xx..x...x.x.x....x.x..x.x...xx..
.x.x...x.x..x.x..x..x......xxx....x..
xx..x.x....xx.......xx..xx.x..x.x....
.x.x.x.x..x.x....xx.x....xx....xx..x.
.x.x....x.....xx.xx..x.x...x..x.x..x.
.........x.xx....x...xx.x.x........xx
xxx...x.x....x....x.xx..x....xxxx..x.
xx..x......xx.......x.x.x.xx..x.xx.x.
.x......xxx..x.x...x.x...x.x....x..x.
.xx..x..x...xx..x.x...x.x..x..x..x...
..x...x.x.xx.x..x..x.x..x...x....x..x
x..xx..x.....xx..x.x..x.x...x........
.xx.xxx..x...xx..x.x.....xxx..x....xx
....x...xxx...x.x....xx...x...xx.x..x
..x..x...x..xx.....xx.x..x......xx.xx
..x..x....x...x.xx..x.x..x..x..x...x.
....x..x...x.x...xxxx...x.x...xx..x..
....xx...x.x.xx..x.....xxx...x..x.x..
x.....xxx...x.x...x.x...x...x.xx..x..
.x...xx..x..x.x...x..x...xx.x..x..x..
x...x.x..x...x.x.x.....xx.x..x...xx..
.x.x..x..x..x.x..x....x..x...x.xx..x.
..xx...x.x..x..x.x..x.....x...x.x.xx.
x.......xxx.x..x...xx..x...x.x..x....
x.xx......x...x.x.xx..x.x..x...x.x..x
..x.x..x..x.x..x...x..x...xx.x....xx.
.x...x..xx..x..x..x..x..x..x..x.x..x.
..x...xx...x...xx.x....xx...x....x...
xx..xx....xx.x..x.x...x..x..x..x..x..
...xxx..x.x.....xx.x.....xxx..x..x...
x..x..x..xx...x.x...x.x.x...x.......x
x.xxx....xx..x..x...x.x...x..xx..x...
x.x..x.x....x.x.x..x..x..x..x..x.x...
x..x..x.....x...x.x..x...x.xx...x...x
xxx..x..x......x..xx.x.x...x.x.x.x..x
...x..x......xxxx..x...x.x......xxx.x
...x..x.x..x...x.x..x...x.x.....x.x..
....xx.xx..xx.......x..x.x....xx.xxx.
.x..xx..x....xx..x..x......x....x...x
xx.x..xx..xx......x.x..x......x.x.xx.
x..x.x......xxx.x....x....x...xxxx.x.
.x...x.x...x...xx..x..x.x.x......xx..
xx.x..x..x..x..x..x.x....x.x..x.x....
..xxx....x....x.xx.xx..x....xx..x..x.
.x..x..x.x..x..x.......x.x.x.x.....xx
xx...xx...x......x.x.xx......xxx..x.x
...x....x...xx..x..x..xx.x....xxx..x.
.x..x...x.x.x....x.x..x.x....xx....xx
....x.x.x...xx.x...x..x...x.x.x..x..x
..x..x.x.....xx.x.x..x.....x..x.x.x.x
.x..x....xx..x..x...x...x.xx..x..x...
.x.x..xx..x..x..x...x.x...xx..x..x...
..xx.x..x..x...xx...x.x...xx..x...x..
x.x..x..x..x....xx.x..x..x.....xxx...
x....x...xxx..x.x...x...x.x.x..x.x...
...xxx....xx..x..x...x...xx..x....xx.
.x..x.x.x......x...xxxx...x.x..x..x..
..xx.x..x...x.x.....x.x..x...xxx.....
..xxxx..x..x..x..x..x.....x..x..x.xx.
x...x..xx...x.x..x...x.x..x...x.x...x
.x.x..x..x.....xx...x..xx......xx...x
xx.x..x...x..x..xx..x..x.....xx....xx
x..x...x..x..x..xx..x.......x.x.xx..x
.x.....xx.x....xx.x.x..x...x..x..x..x
....xxx....xx....x.x.x...x.x.x..x....
.xx.x.x..x..x...x.x...x.x.x..x...x.x.
.....xx.x.x.x..x......xx.x.x.x..x....
x..xx..x...x.x.x..x..x...x.x....x..x.
..x.x.x.x..x.x..x...x.x..x..x....x.xx
.x..x....xx..x......x.x..x...xxx..x..
...xx.xx..x..x..x......xx..xx.x..x..x
..x.x..x...x..x.x..x....xx..x..x.x...
.x..xx..x.x...x..x.x......xxx.x..x..x
......x.x....x.xx.xx.....xx.x.x..x..x
...x.....x.x.xx..x.x...x....x.x.xx..x
...x.x...x.x..x.x..x...x.x..x..x.....
xx...xx.x..x....xx...xx......xx..x.x.
.....xxx.x.x..x..x..x.x..x....x..x..x
x..x......xx....xxx..x..xx..x..x....x
.x........xxx.xx.x..x..x....xx.x..x..
..x.x....xxx..x...x.x...x........xxx.
xx..x.x...x.......xx.xx....xxx..x...x
x..x..x..x..x.........x.xxxx.x...x...
x..x.x.x..x.x..x...xx...x..x..x..x...
xx..x.x....x.x...xx.....x..x.xx..x.x.
....xxx..x...x.x.....x.xx...xx.....xx
.x...x.x.x...x.x....xx..x..x.x..x..x.
....xx..x.x...xx.....xx.x..x..x..x.x.
...xx..x..x..x.x........x....xx.xxxx.
...xx..x...x......x..x.xx.x....x....x
.xx.x..x....x...x.xxx.x...x.x..x.x..x
...xx..x...x....xx...xx.x.....xx.x...
x.x...x..xx..x...x.x..x...xx..x...x..
.....x.x.x..xx.x....xx...x...x.xx.x.x
....x.x.......x..x.xxx..xx...x.x.x..x
..x..x.....xx.x..x.x..x...x.x..x..x.x
..x..x...x.x..x...x.x.x...x.x..x..x..
...x..x.xx.x.....xx....x.x...x..xxx..
x....xx.x....x.x.x..x..x...xx.....xx.
...x.xx.x..x...x.x....x..xx...x...xx.
x..x..x..x.x..x...x.x..x..x.....xx...
x...x.xx..x.x..x.x..x..x....xx..x.x..
.x.......x...xxx....x.x...xx.x...xxx.
x...x.x...x..x..x..xx......xxx..x...x
.x.x..x..x...x........x..xx..x.xx.x.x
.....x.xx.x...x.x.x..x..x.x..x..x..x.
.....x..xxx...xx..x...x.x..x..x..x..x
...x..x.x...x...xxx.....x..xx..xx..x.
......x.xxx....xx..x.x..x..x....x..x.
xx....xx...x.x..x..x.x..x..x...x.x..x
.x..x...x.x..x..x..x..x.....x.xx.x...
x.x...xx....xx...x....x....x...xxx.x.
x.x..x.x..x..x..x..x..x...xx..x...x.x
...x.x........x.xxx.....x..xx..xxx...
.xx..x...x..xx..x..x....xx..x....xx..
.xx..x..x...x.....x.xxx..x....xx..x.x
..x..x..x..x..x..x.......xx......xx..
xx.x.x.x..x.x......xx..x..xxx.....x.x
x..x..x..x..x.x.....xx..x.x..x.x..x..
样例输出
122