thanhchauns2's blog

Can anyone help me with this problem?
By thanhchauns2, history, 4 years ago, In English

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.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by thanhchauns2 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by thanhchauns2 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by thanhchauns2 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry for the input, codeforces use '$' and '*' for formating the text so I have to take a detour T-T

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can you please specify the constraints

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by thanhchauns2 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    You can use 0-1 BFS in place of Dijkstra.

    → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

This is same as problem J here if someone wants to submit.

→ Reply