### thanhchauns2's blog

By thanhchauns2, history, 19 months ago,

Given a map of a dungeon, your task is to take all TWO diamonds in the dungeon.

Find the minimum number of gates you have to open to take all the diamonds.

Note: It can be more than one gate to go into the dungeon from the outside.

You can move up, down, left, right.

• The letter '.' means blank space, you can move on it

• The letter '*' means blockade, you have to go around it

• The letter '#' means there's a gate at that place, you need it opened to go through it

• The letter '$' means the diamond. Input format: • First line is two number N and M — the dungeon has the size N*M. (2 ≤ N,M ≤ 100) • N lines following, represent the map of the dungeon. Output format: • A single integer — the minimum number of gates you have to open. Example input: 5 9 ****#**** ..#.#.. ****.**** $#.#.#$ Sorry for the input, you can see read the input here : https://ideone.com/EXk0Wh Example output: 4 Thank you guys, hope you have a great standing in the next contest. • +7  » 19 months ago, # | 0 Auto comment: topic has been updated by thanhchauns2 (previous revision, new revision, compare).  » 19 months ago, # | 0 Auto comment: topic has been updated by thanhchauns2 (previous revision, new revision, compare).  » 19 months ago, # | 0 Auto comment: topic has been updated by thanhchauns2 (previous revision, new revision, compare).  » 19 months ago, # | ← Rev. 2 → 0 Sorry for the input, codeforces use '$' and '*' for formating the text so I have to take a detour T-T
•  » » 19 months ago, # ^ |   0 can you provide the link of the problem too.
•  » » » 19 months ago, # ^ |   0 It's a local website for my university. I'm not sure if there's any website have the problem in English. (Vietnamese): https://code.ptit.edu.vn/student/question/DSA09040
 » 19 months ago, # |   +6 Can you please specify the constraints
 » 19 months ago, # |   0 Auto comment: topic has been updated by thanhchauns2 (previous revision, new revision, compare).
 » 19 months ago, # |   +3 I have some idea. May be wrong. Let us construct a graph from the matrix, where each gate has a edge weight 1 and each empty cell has a edge weight 0. Now taking 1st diamond as source run dijkstra and taking other diamond as source run another dijkstra. Now the diamonds will meet at a point and leave the dungeon together(Meeting point may be the leaving gate as well) . We can brute force that meeting point, find individual distances to the meeting point(already computed using dijkstra) (let it be d1+d2). Now just find the min distance from that meeting point to any of the nearest leaving pont from the dungeon, which can be easily be precomputed using multisource dijkstra taking leaving points as source, let it be dx. Now the answer for that meeting point is d1+d2+dx, find min among them.
•  » » 19 months ago, # ^ |   0 I think before telling solution to any problem asked on online platform you should verify that it's not from any ongoing contest. A lot of times, I have seen people asking for solutions to ongoing contests like this. thanhchauns2 can you please share link of problem to verify this thing.
•  » » » 19 months ago, # ^ | ← Rev. 4 →   0 Yeah sure, it's a problem from a local website and it's not from any ongoing contest. Link to the problem (Vietnamese) https://code.ptit.edu.vn/student/question/DSA09040
•  » » » » 19 months ago, # ^ |   +3 Next time whenever you ask any problem of cf, add link to problem at the end. This will help you getting reply quickly and also avoiding downvotes.
•  » » 19 months ago, # ^ |   +9 You can use 0-1 BFS in place of Dijkstra.
 » 19 months ago, # |   +4 This is same as problem J here if someone wants to submit.
•  » » 19 months ago, # ^ |   0 Thank you so much bro.