Under construction

Still being built. Things may change

Treasure Island

Interview

Time limit1sMemory limit512 MB

Summary
Given a grid of land and water cells, find the largest shortest-path distance between two connected land cells (grid diameter via multi-source BFS).
Level

Medium4 of 10

Topics
BFS, Graph, Matrix
Solved
No attempts yet

Problem

Captain Hook has found a rectangular treasure map divided into cells. Each cell is marked as land (L) or water (W). From a land cell, movement is allowed only to an edge-adjacent land cell, and each move takes one hour.

The treasure is buried in two land cells whose shortest travel time between them is as large as possible. Among all pairs of land cells that can reach each other, find the maximum shortest travel time.

Input

The first line contains the height H and width W of the treasure map, separated by a space. The next H lines contain the map, using L and W with no spaces between characters.

Both the height and the width of the map are at most 50.

Output

Print the shortest travel time between the two land cells where the treasure is buried.

Examples1

  1. Example 1

    Input
    5 7
WLLWWWL
LLLWLLL
LWLWLWW
LWLWLLL
WLLWLWW
    Expected output
    8