title: "Wave Algorithm" (based in Lee's Algorithm) in C
body: <p>I'm writing a program calculation the shortest way from point A to point B.
  I have a map (matrix) with values:</p>
  
  <ul>
  <li>0 is block (wall, no way to pass);</li>
  <li>1 is free way (you can pass);</li>
  <li>11 is point A (start point);</li>
  <li>22 is point B (finish point).</li>
  </ul>
  
  <p>I've read a few articles how it should work and tried to realize my own version but got stacked.</p>
  
  <p>In the code below I declare 2 arrays: an array with Map and changed array "visited" while running program demonstrating visited points.</p>
  
  <p>I check the cells in 4 directions (not diagonals) for 1 or 0. If it's 1 (possible to pass), I increase the counter for 1. For do not count the previous cell I'm trying to avoid it by the condition.</p>
  
  <p>As a result I wanna see "visited" matrix with a few lines which shows the way to reach to the point B (1, 2, 3, ... 15).</p>
  
  <p>Right now my map doesn't look like correct, not even close.</p>
  
  <p>What have I missed in my algorithm, what should I take into account and how to fix my program?</p>
  
  <p>Thank you.</p>
  
  <p>P.S. I wrote a few functions implementing a new array with 0 values, counting free to go cells and printing arrays.</p>
  
  <p>main.c:</p>
  
  <pre><code>    #include &lt;stdbool.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;stdio.h&gt;
  
  #define WIDTH 8
  #define HEIGHT 8
  
  int mapZero(int map[WIDTH][WIDTH]);
  int mapPrint(int map[WIDTH][HEIGHT]);
  int mapInit(int map[WIDTH][WIDTH]);
  int findFreeToGoCells(int map[WIDTH][WIDTH]);
  
  int main(int argc, char * argv[])
  {
      short int prevPosition;
      short int currPosition;
      short int nextPosition;
      short int lastPosition;
  
      int visited[WIDTH][HEIGHT];
  
      unsigned int count;
      unsigned int max;
  
      mapZero(visited);
  
      int map[WIDTH][HEIGHT] =
      {
          { 11, 1, 1, 1, 1, 0, 0, 1 },
          { 0, 1, 1, 1, 1, 1, 0, 1 },
          { 0, 0, 1, 0, 1, 1, 1, 0 },
          { 1, 0, 1, 1, 1, 0, 1, 1 },
          { 0, 0, 0, 1, 0, 0, 0, 1 },
          { 1, 0, 1, 1, 1, 0, 0, 1 },
          { 0, 0, 0, 0, 1, 0, 0, 1 },
          { 0, 1, 1, 1, 1, 1, 1, 22 },
  
      };
  
      printf("Matrix of zeroed-visited cells:\n\n");
      mapPrint(visited);
  
      printf("Matrix of the map:\n\n");
      mapPrint(map);
  
      printf("Ways: %d\n", findFreeToGoCells(map));
  
      prevPosition = map[0][0];
      currPosition = 0;
  
      count = 0;
      max = WIDTH * HEIGHT;
  
      for (int i = 0; i &lt; WIDTH; ++i)
      {
          for (int j = 0; j &lt; HEIGHT; ++j)
          {
              if (((i &gt;= 0) &amp;&amp; (i &lt; WIDTH)) &amp;&amp; ((j &gt;= 0) &amp;&amp; (j &lt; HEIGHT)))
              {
                  // [i + 1][j] 
                  if (map[i + 1][j] == 1)
                  {
                      map[i][j] = prevPosition;
                      if (prevPosition)
                          visited[i + 1][j] = count++;
  
                  }
                  if (map[i + 1][j] == 0)
                  {
                      visited[i + 1][j] = map[i + 1][j];
                  }
  
                  // [i - 1][j]
                  if (map[i - 1][j] == 1)
                  {
                      map[i][j] = prevPosition;
                      if (prevPosition)
                          visited[i - 1][j] = count++;
                  }
                  if (map[i - 1][j] == 0)
                  {
                      visited[i - 1][j] = map[i - 1][j];
                  }
  
                  // [i][j + 1]
                  if (map[i][j + 1] == 1)
                  {
                      map[i][j] = prevPosition;
                      if (prevPosition)
                          visited[i][j + 1] = count++;
                  }
                  if (map[i][j + 1] == 0)
                  {
                      visited[i][j + 1] = map[i][j + 1];
                  }
  
                  // [i][j - 1]
                  if (map[i][j - 1] == 1)
                  {
                      map[i][j] = prevPosition;
                      visited[i][j - 1] = map[i][j - 1];
                      if (prevPosition)
                          visited[i][j - 1] = count++;
                  }
                  if (map[i][j - 1] == 0)
                  {
                      visited[i][j - 1] = map[i][j - 1];
                  }
  
              } // map borders check (finished)
                //count++;
          }
      }
  
      printf("count: %d\n", count);
  
      if (count &gt; 1000)
      {
          printf("The way couldn't be found\n");
      }
      else
      {
          printf("Matrix of visited cells:\n\n");
          mapPrint(visited);
          //printf("Short way: %d\n", findShortWay(map[7][7]));
      }
      printf("Ways: %d\n", findFreeToGoCells(visited));
  
      system("pause");
      return 0;
  }
  
  int mapZero(int map[WIDTH][WIDTH])
  {
      for (int i = 0; i &lt; WIDTH; ++i)
      {
          for (int j = 0; j &lt; HEIGHT; ++j)
          {
              map[i][j] = 0;
          }
      }
  }
  
  int mapPrint(int map[WIDTH][HEIGHT])
  {
      for (int i = 0; i &lt; WIDTH; ++i)
      {
          for (int j = 0; j &lt; HEIGHT; ++j)
          {
              printf("%2d  ", map[i][j]);
          }
          printf("\n\n");
      }
      printf("\n");
      return 0;
  }
  
  int findFreeToGoCells(int map[WIDTH][WIDTH])
  {
      int count = 0;
      for (int i = 0; i &lt; WIDTH; ++i)
      {
          for (int j = 0; j &lt; HEIGHT; ++j)
          {
              if (map[i][j] == 1 || map[i][j] == 99) count++;
          }
      }
      return count;
  }
  </code></pre>
  
  <p>Here the shortest way is always 15 cells</p>
  
  <p><a href="https://i.stack.imgur.com/ZK08x.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ZK08x.png" alt="enter image description here"></a></p>