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.
About the map:
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.
Auto comment: topic has been updated by thanhchauns2 (previous revision, new revision, compare).
Auto comment: topic has been updated by thanhchauns2 (previous revision, new revision, compare).
Auto comment: topic has been updated by thanhchauns2 (previous revision, new revision, compare).
Sorry for the input, codeforces use '$' and '*' for formating the text so I have to take a detour T-T
can you provide the link of the problem too.
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
Can you please specify the constraints
Auto comment: topic has been updated by thanhchauns2 (previous revision, new revision, compare).
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.
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.
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
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.
You can use 0-1 BFS in place of Dijkstra.
This is same as problem J here if someone wants to submit.
Thank you so much bro.