CountDeadEnds is a maze code snippet that counts all the dead ends in a maze, for example the mazes created by CreateMaze/CreateSloppyMaze.

Project and source code

Operating system: Ubuntu 10.04 LTS Lucid Lynx

IDE: Qt Creator 2.0.0

Project type: Qt4 GUI Application

Compiler: G++ 4.4.1

Libraries used:

Qt: version 4.7.0 (32 bit)
STL: from GCC, shipped with Qt Creator 2.0.0


#include <vector>



//From http://www.richelbilderbeek.nl/CppCountDeadEnds.htm

const int CountDeadEnds(const std::vector<std::vector<int> >& maze)

{

  const int size = maze.size();



  int nDeadEnds = 0;



  for (int y=1; y!=size-1; ++y)

  {

    for (int x=1; x!=size-1; ++x)

    {

      if (maze[y][x] != 0) continue; //Continue if here is a wall

      const int nWalls

        = (maze[y+1][x  ] == 1 ? 1 : 0)

        + (maze[y-1][x  ] == 1 ? 1 : 0)

        + (maze[y  ][x+1] == 1 ? 1 : 0)

        + (maze[y  ][x-1] == 1 ? 1 : 0);

      if (nWalls == 3) ++nDeadEnds;



    }

  }

  return nDeadEnds;

}

Go back to Richel Bilderbeek's C++ page.

Go back to Richel Bilderbeek's homepage.

(C++) CountDeadEnds

Project and source code