$2$

Need help with Python code with best performance

There is a cleaning robot in a room. The room is described by an array of strings, where $"."$ represents an empty floor area, $"$ an area the robot cannot enter $($obstacles such as walls or furniture$),$ and $"**"$ is the initial position of the robot. It is possible to reach all empty floor areas from the robot's initial position. Rows are numbered from $0$ to $R-1$ from top to bottom, and columns are numbered from $0$ to $C-1$ from left to right $($in other words, field $(0,0)$ is the upper$-$left corner$).$ The room is always surrounded by walls $("$#$"),$ which means that there are always walls in columns $0$ and $C-1$ and in rows $0$ and $R-1.$

Your task is to generate a sequence of commands consisting of moves: up $("^"),$ down $("$v$"),$ left $("<mi\; id="EditorElement\_2370969">"</mi><mi\; id="EditorElement\_2370970">)</mi>$ and right $(">"),$ such that the robot will clean all the required fields $($depending on the subtask, full room or just the borders of the room$).$ The robot cleans all the fields it visits, including the field the robot starts on$.$ The robot should never step into any obstacles, but it can enter the same field multiple times. The robot may finish at any field $($it does not have to return to the starting point$).$

Write a function:that, given an array room consisting of R strings, each of length C$,$ and an integer subtask representing the type of subtask the function should solve $($subtasks a

Subtask $1$

Room shape: a simple rectangle;

Starting position: the top$-$left corner;

Area to be cleaned: the border of the room $($fields adjacent to the walls$).$

For example, for room $=["$#######$","$#$*....$ #$","$#$.....$ #$","$# $.....$ #$","$#######$"],$ one of the possible sequences that your function may return is: $">>>>$Vve

A graphical representation of this example is shown in the picture below. The expected areas to be cleaned are colored in blue, and the blocked areas are in gray, marked by $"x".$ The robot is allowed to enter areas that are not required to be cleaned $($that are white in the picture$).$

Subtask $2$

changes saved

Subtask $2$

Room shape: a simple rectangle;

Starting position: no constraints $($can be any field$)$;

Area to be cleaned: the whole floor.

For example, for room $=["$#######$","$# $.....$ #$","$# $..*..$ #$","$# $.....$ #$","$# $.....$#$","$######$"],$ one of the possible sequences that your function

Subtask $3$

Room shape: a rectangle divided into two smaller rectangular parts by a vertical $($top$-$to$-$bottom$)$ wall, connected by a single$-$field passage;

Starting position: no constraints $($can be any field$)$;

Subtask $3$

Room shape: a rectangle divided into two smaller rectangular parts by a vertical $($top$-$to$-$bottom$)$ wall, connected by a single$-$field passage;

Starting position: no constraints $($can be any field$)$;

Area to be cleaned: the whole floor.

For example, for room $=["$#######$","$#$.*.$#$..$ #$","$# $......","$#$......$ #$","$#######$"],$ one of the possible sequences that your function may return is: $"$

Subtask $5$

Room shape: any shape. The room may also contain some additional obstacles besides the walls $($for example furniture$)$;

Starting position: no constraints $($can be any field$)$;

Area to be cleaned: the whole floor.

For example, for room $=["$########$","$### $....$ #$","$### $..$ #$.$ #$","$# $....*.$ #$","$#$...$##$.$#$","$########$"],$ one of the possible sequences that your function may return is: re described below$),$ returns the string representing the required sequence of commands.

Constraints

Assume that:

each string in array room consists only of the following characters: $".","$#$"$ and $"*"$;

there is exactly one starting point, marked by $"*"$;

all empty fields can be reached from the starting point;

$R$ and $C$ are integers within the range $[3.\mathrm{.}50]$;

the generated sequence can not contain more than $100,000$ commands.

Subtasks may specify additional assumptions.

Subtasks:

Your solution's score will depend on how many subtasks it is able to solve. Each subtask is worth an equal number of points $(20\%).$ Each subtask may differ in three categories:

expected area to be cleaned;

room shape;

starting point of the robot.

Subtask $1$

Room shape: a simple rectangle;

Starting position: the top$-$left corner;

Area to be cleaned: the border of the room $($fields adjacent to the walls$).$