How to implement a wave algorithm for finding the shortest path in C++?

Question

C++ / C#

Good day.
Need to implement a wave algorithm to find the shortest path in the maze. I do not understand how to implement a wave in the matrix. Help.

Answer 1

Wikipedia has a pseudo-code of the algorithm, which can be implemented using standard C/C++ language constructs.
Lee Algorithm
Initialize a two-dimensional array of type int. Use cell value -1 for maze walls. Store the start and end indexes of the maze in separate variables.
Wave propagation and recovery is fully consistent with the description of the algorithm in the wiki. The only difficulty with wave propagation is determining the last labeled cells. To begin with, you can use the full enumeration of the array, then complicate it - apply recursive functions or remake the cycles competently.

Answer 2

Recently I wrote a paper on wave) An extremely simple way:
1. assign the starting point length = 0, the rest - an unattainable number (for example, -1). "Walls" around the edges - optional.
2. Depending on the selected neighborhoods (Moore / Moore order or Neumann. In Moore, a couple of lines of code more are written in the loop), you check each of the nearest points (through ifelse / switch - at will and possibilities. ). If it is equal to -1, you assign the value length + 1 to it. If it is not equal to - 1 (that is, if we have already written the distance from the starting point length into it) - skip.
3. length += 1;
The easiest way to imagine (or display) a rectangular field (it is also a two-dimensional array), where all cells are initially equal to -1, and at the start point is 0. Through while, check for unwritten cells (-1) and run the above described loop.
PS: at first I also tried to search on sites, everywhere an invalid rewrite with an abstruse code for eight pages. I spat, I sat down and figured it out myself (code for 20 lines), which I advise everyone.