Hexagonal Maze

Statement

Goal

You are in a maze, made of hexagonal cells.
The following grid :

4 4
ABCD
EFGH
IJKL
MNOP

has to be understood like this :

  / \   / \   / \   / \
 /   \ /   \ /   \ /   \
|     |     |     |     |
|  A  |  B  |  C  |  D  |    Line 0
|     |     |     |     |
 \   / \   / \   / \   / \
  \ /   \ /   \ /   \ /   \
   |     |     |     |     |
   |  E  |  F  |  G  |  H  | Line 1
   |     |     |     |     |
  / \   / \   / \   / \   /
 /   \ /   \ /   \ /   \ /
|     |     |     |     |
|  I  |  J  |  K  |  L  |    Line 2
|     |     |     |     |
 \   / \   / \   / \   / \
  \ /   \ /   \ /   \ /   \
   |     |     |     |     |
   |  M  |  N  |  O  |  P  | Line 3
   |     |     |     |     |
    \   / \   / \   / \   /
     \ /   \ /   \ /   \ /

This means each cell has 6 neighbours : for example, cell F is surrounded by B, C, E, G, J, K.
The grid is periodic, if you go left you appear on the right if there is no wall, and vice versa, similarly with up/down.
So cell B also has 6 neighbours : M, N, A, C, E, F.
Even lines are left-aligned, odd lines are right-aligned.

You are given a grid made by walls and free spaces, you have to draw the shortest path to go from the start to the end.
There may be more than one path, but only one shortest path.
There is always a solution.

The grid contains following symbols :
# : wall
_ : free space
S : start
E : end
You must output the same grid with symbols . on cells which are on the shortest way.

Input

First line: two integers w and h, width and height of the grid.

h following lines: the grid.

Output

h lines : the grid with the answer.

Constraints

4 ≤ w, h ≤ 25
h is always even.

Example

Input

5 6
#####
#S#E#
#_#_#
#_#_#
#___#
#####

Output

#####
#S#E#
#.#.#
#.#.#
#_..#
#####

Comments

11 Comments

PatrickMcGinnisII Unnamed CodinGamer

almost 2 years ago

I really enjoyed this one. The search space is limited enough that I didn't have to use anything fancy, or even backtrace. I could see a harder version forcing us to use a version of your novel solution. I'm not sure if you change the order in which you check neighbors matters in your solution. Does it?

Remi. Unnamed CodinGamer

No, the order doesn't matter. It'd matter if there were several shortest pathes, but it was not wanted. How do you suggest to do an harder version ? The contribution is now approved but i want to do other mazes based on hexagonal grid or cells.

DaNinja Unnamed CodinGamer

✅ Approved the contribution. Comment: Interesting challenge to run a BFS on a hex grid

Westicles Unnamed CodinGamer

✅ Approved the contribution. Comment: Nicely done.

I_love_CoC Unnamed CodinGamer

✅ Approved the contribution. Comment: the author seems to be really dedicated to his work and made a lot of efforts to explain clearly the goal of his puzzle. Nice work

chouch Unnamed CodinGamer

Looks good. You did not precise in the statement if there is only one shortest path so I tested it and there is indeed only one. Maybe it's worth mentionning it. Also i miss some interesting test case like these : // blocked ? 4 5 #### #S## ##_# #E## #### // blocked v2 ? 4 5 #### ##S# #_## ##E# #### // corner ? 4 4 #### ##S# #E#_ _##_ // corner v2 ? 4 4 #### #S## _#E# _##_

Thank you. I've just mentionned the only one shortest path. The corner is tested by the "Everything" test and validator : [bottom left => top left => top right] in test, and [bottom right => top left] in validator. Do you think i really have to do specific tests ? I can't add the blocked test because there is always a solution, but the first test and validator check the possible diagonals.

5DN1L Unnamed CodinGamer

Suggest to use "similarly" instead of "idem".

Done. Thanks