(Solved): This python code solve this problem, but exceed the time limit for most cases! can you help me ...

This python code solve this problem, but exceed the time limit for most cases! can you help me to revise this code to solve this problem using graph theory in python with the limitations provided!.

the problem:

Python code:

please revise the code to run with the time and memory limitations with correct output.

time limit per test: 2 secondso memory limit per test: 1024 megabytes input: standard input output: standard output \( \mathrm{Yi} \) and Han are two swans living on a lake. They are good friends and often play together. One day they woke up and found out that because of the snow last night, they were separate in two different areas by ice. The lake can be viewed as a \( r \times c \) grid. We will use " \( \mathrm{X} \) " to represent a cell of ice. and "." a cell as water. At the beginning, Yi and Han are both at a cell of water. Every day, some ice cells " \( \mathrm{X} \) " will melt. An ice cell " \( \mathrm{X} \) " melts if and only if in the previcus day, at least one of its adjacent grids is water. Here "adjacent" means on the top, bottom, left and right, at most 4 of them. An example of the ice melting process is shown above. Yi and Han can both swim to any adjacent water cell from their current position, but they cannot swim to any ice cells. They both swim very fast so that they can arrive at any cell on the lake instantly as long as two cells are connected with water cells. Given the initial position of Yi and Han, and the current status of the lake, decide that at which day \( Y i \) and Han can meet again. Input The first line contains two integers \( r \) and \( c, 1 \leq r, c \leq 1500 \). The following \( r \) lines each contains \( c \) characters, which describes the initial status of the lake. " "means a water cell. " \( X \) " means an ice cell, "L" means a swan. Output The output only contains one integer \( t \), which means that after \( t \) days, \( Y \) and Han can meet.