Scribd
Upload
7 views3 pages

Labyrinth and Network Pathfinding Solutions

The document describes two problems involving navigation and communication in a labyrinth and a network of computers, respectively. The first problem requires finding a path to the boundary of a labyrinth while avoiding monsters, while the second problem involves determining if a message can be sent between two computers and finding the minimum route. Additionally, there is a hard problem related to finding the centroid of a tree, considering both even and odd cases.

Uploaded by

dishantmarchant12345
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views3 pages

Labyrinth and Network Pathfinding Solutions

The document describes two problems involving navigation and communication in a labyrinth and a network of computers, respectively. The first problem requires finding a path to the boundary of a labyrinth while avoiding monsters, while the second problem involves determining if a message can be sent between two computers and finding the minimum route. Additionally, there is a hard problem related to finding the centroid of a tree, considering both even and odd cases.

Uploaded by

dishantmarchant12345
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

LAB->(GRAPHS)

1.(EASY)
You and some monsters are in a labyrinth. When taking a step to some direction in the labyrinth,
each monster may simultaneously take one as well. Your goal is to reach one of the boundary
squares without ever sharing a square with a monster.

Your task is to find out if your goal is possible, and if it is, print a path that you can follow. Your
plan has to work in any situation; even if the monsters know your path beforehand.

Input
The first input line has two integers nn and mm: the height and width of the map.

After this there are nn lines of mm characters describing the map. Each character is . (floor), #
(wall), A (start), or M(monster). There is exactly one A in the input.

Output
First print "YES" if your goal is possible, and "NO" otherwise.

If your goal is possible, also print an example of a valid path (the length of the path and its
description using characters D, U, L, and R). You can print any path, as long as its length is at
most n⋅mn⋅m steps.

Constraints
●​ 1≤n,m≤1000
●​ m≤10001≤n,

Example
Input:

58
########
#M..A..#
#.#.M#.#
#M#..#..
#.######

Output:

YES
5
RRDDR

2.
(EASY)

Syrjälä's network has nn computers and mm connections. Your task is to find out if Uolevi can
send a message to Maija, and if it is possible, what is the minimum number of computers on
such a route.

Input
The first input line has two integers nn and mm: the number of computers and connections. The
computers are numbered 1,2,…,n1,2,…,n. Uolevi's computer is 11 and Maija's computer is nn.

Then, there are mm lines describing the connections. Each line has two integers aa and bb:
there is a connection between those computers.

Every connection is between two different computers, and there is at most one connection
between any two computers.

Output
If it is possible to send a message, first print kk: the minimum number of computers on a valid
route. After this, print an example of such a route. You can print any valid solution.

If there are no routes, print "IMPOSSIBLE".

Example
Input:

55
12
13
14
23
54

Output:

3
145

Q3(Hard)
FIND THE CENTRE,CENTROID OF A TREE.
(
TAKE CARE OF EVEN ODD CASES
)

You might also like