- Prepare
- Algorithms
- Dynamic Programming
- Mr K marsh

# Mr K marsh

# Mr K marsh

Mr K has a rectangular plot of land which may have marshes where fenceposts cannot be set. He wants you to find the perimeter of the largest rectangular fence that can be built on this land.

For example, in the following grid, marks a marsh and marks good land.

```
....
..x.
..x.
x...
```

If we number the rows and columns starting with , we see that there are two main areas that can be fenced: and . The longest perimeter is .

**Function Description**

Complete the *kMarsh* function in the editor below. It should print either an integer or `impossible`

.

kMarsh has the following parameter(s):

*grid*: an array of strings that represent the grid

**Input Format**

The first line contains two space-separated integers and , the grid rows and columns.

Each of the next lines contains characters each describing the state of the land. 'x' (ascii value: 120) if it is a marsh and '.' ( ascii value:46) otherwise.

**Constraints**

**Output Format**

Output contains a single integer - the largest perimeter. If the rectangular fence cannot be built, print **impossible**.

**Sample Input 0**

```
4 5
.....
.x.x.
.....
.....
```

**Sample Output 0**

```
14
```

**Explanation 0**

The fence can be put up around the entire field. The perimeter is .

**Sample Input 1**

```
2 2
.x
x.
```

**Sample Output 1**

```
impossible
```

**Explanation 1**

We need a minimum of 4 points to place the 4 corners of the fence. Hence, impossible.

**Sample Input 2**

```
2 5
.....
xxxx.
```

**Sample Output 2**

```
impossible
```