Блог пользователя thanhchauns2

Автор thanhchauns2, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Can you please specify the constraints

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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