Алгоритм Ли

const int W      = 12;         // ширина рабочего поля
const int H      =  8;         // высота рабочего поля
const int WALL   = -1;         // непроходимая ячейка
const int BLANK  = -2;         // свободная непомеченная ячейка
 
int px[W * H], py[W * H];      // координаты ячеек, входящих в путь
int len;                       // длина пути
int grid[H][W];                // рабочее поле
 
// Перед вызовом lee() массив grid заполнен значениями WALL и BLANK
 
bool lee(int ax, ay, bx, by)   // поиск пути из ячейки (ax, ay) в ячейку (bx, by)
{
  int dx[4] = {1, 0, -1, 0};   // смещения, соответствующие соседям ячейки
  int dy[4] = {0, 1, 0, -1};   // справа, снизу, слева и сверху
  int d, x, y, k;
  bool stop;
 
  // распространение волны
  d = 0;
  grid[ay][ax] = 0;            // стартовая ячейка помечена 0
  do {
    stop = true;               // предполагаем, что все свободные клетки уже помечены
    for ( y = 0; y < H; ++y )
      for ( x = 0; x < W; ++x )
        if ( grid[y][x] == d )                         // ячейка (x, y) помечена числом d
        {
          for ( k = 0; k < 4; ++k )                    // проходим по всем непомеченным соседям
            if ( grid[y + dy[k]][x + dx[k]] == BLANK )
            {
              stop = false;                            // найдены непомеченные клетки
              grid[y + dy[k]][x + dx[k]] = d + 1;      // распространяем волну
            }
        }
    d++;
  } while ( !stop && grid[by][bx] == BLANK );
 
  if (grid[by][bx] == BLANK) return false;  // путь не найден
 
  // восстановление пути
  len = grid[by][bx];            // длина кратчайшего пути из (ax, ay) в (bx, by)
  x = bx;
  y = by;
  d = len;
  while ( d > 0 )
  {
    px[d] = x;
    py[d] = y;                   // записываем ячейку (x, y) в путь
    d--;
    for (k = 0; k < 4; ++k)
      if (grid[y + dy[k]][x + dx[k]] == d)
      {
        x = x + dx[k];
        y = y + dy[k];           // переходим в ячейку, которая на 1 ближе к старту
        break;
      }
  }
  px[0] = ax;
  py[0] = ay;                    // теперь px[0..len] и py[0..len] - координаты ячеек пути
  return true;
}
 
...
 
lee(3, 6, 3, 0);                 // поиск пути из ячейки (3,6) в ячейку (3, 0) (см. рис.)

do {
    stop = true;               // предполагаем, что все свободные клетки уже помечены
    for ( y = 0; y < H; ++y )
      for ( x = 0; x < W; ++x )
        if ( grid[y][x] == d )                         // ячейка (x, y) помечена числом d
        {
          for ( k = 0; k < 4; ++k )                    // проходим по всем непомеченным соседям
            if ( grid[y + dy[k]][x + dx[k]] == BLANK )
            {
              stop = false;                            // найдены непомеченные клетки
              grid[y + dy[k]][x + dx[k]] = d + 1;      // распространяем волну
            }
        }
    d++;
  } while ( !stop && grid[by][bx] == BLANK );