Finds shortest paths in given map.

input.txt

5 3
0 0 0
0 1 0
2 1 3
0 1 0
0 0 0

Main.cc

// This code reads map from input.txt, finds shortest paths, and writes path
// information to output.txt.

// Map legend:
// 0: Road
// 1: Obstacle
// 2: Starting point
// 3: Destination
// 4: Path

#include <cstddef>
using std::ptrdiff_t;

#include <fstream>
using std::ifstream;
using std::ofstream;

#include <iostream>
using std::cout;
using std::endl;
using std::ostream;

#include <limits>
using std::numeric_limits;

#include <stdexcept>
using std::domain_error;
using std::exception;
using std::logic_error;
using std::out_of_range;

#include <tuple>
using std::get;
using std::make_tuple;
using std::tuple;

#include <vector>
using std::vector;

// Used for indicate invalid position.
constexpr ptrdiff_t Invalid() { return -1; }

// Used for indicate Infinity in determining shortest path.
constexpr ptrdiff_t Infinity() { return numeric_limits<ptrdiff_t>::max(); }

class Map
{
  public:
    enum class Element : unsigned char
    {
        Road,
        Obstacle,
        Start,
        Destination,
        Path
    };

    struct Pos
    {
        ptrdiff_t i, j;

        Pos operator+(Pos const &pos) { return Pos { i + pos.i, j + pos.j }; }
    };

  public:
    // Check whether the given value is valid enum value.
    static inline bool IsValidElement(Element elem)
    {
        return 0 <= static_cast<unsigned char>(elem)
               && static_cast<unsigned char>(elem) < 5;
    }

  private:
    ptrdiff_t       _height, _width;
    vector<Element> _data;

  public:
    ptrdiff_t height() const { return _height; }
    ptrdiff_t width() const { return _width; }

  public:
    Map() : _height(0), _width(0), _data() {}

    Map(ptrdiff_t height, ptrdiff_t width)
        : _height(height), _width(width), _data(height * width, Element::Road)
    {}

  public:
    inline bool IsValidIndex(ptrdiff_t i, ptrdiff_t j) const
    {
        return 0 <= i && i < _height && 0 <= j && j < _width;
    }

    inline bool IsValidIndex(Pos const &pos) const
    {
        return IsValidIndex(pos.i, pos.j);
    }

    Element Get(Pos const &pos) const { return Get(pos.i, pos.j); }

    Element Get(ptrdiff_t i, ptrdiff_t j) const
    {
        return _data.at(i * _width + j);
    }

    void Set(ptrdiff_t i, ptrdiff_t j, Element elem)
    {
        _data.at(i * _width + j) = elem;
    }

    void Set(Pos const &pos, Element elem) { Set(pos.i, pos.j, elem); }

    vector<vector<Pos>> FindPaths() const
    {
        Pos st, ds;
        _ValidateInfo(st, ds);

        vector<vector<Pos>>           rtn;
        vector<tuple<ptrdiff_t, Pos>> stack;
        vector<Pos>                   path_stack;
        ptrdiff_t                     shortest = Infinity();

        Map tmp = *this;

        stack.push_back(make_tuple(ptrdiff_t(1), Pos { st.i, st.j }));

        while (!stack.empty())
        {
            auto  out  = stack.back();
            auto  lvl  = std::get<0>(out);
            auto &curr = std::get<1>(out);
            stack.pop_back();

            for (ptrdiff_t i = lvl - 1, l = path_stack.size(); i < l; ++i)
                tmp.Set(path_stack[i], Get(path_stack[i]));

            path_stack.resize(lvl - 1);
            path_stack.push_back(curr);

            if (Get(curr) == Element::Destination)
            {
                if (shortest > lvl)
                {
                    shortest = lvl;
                    rtn.clear();
                    rtn.push_back(path_stack);
                }
                else if (shortest == lvl)
                    rtn.push_back(path_stack);
            }
            else
            {
                tmp.Set(curr, Element::Obstacle);

                Pos offsets[] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
                for (auto &offset : offsets)
                {
                    auto new_pos = offset + curr;

                    if (IsValidIndex(new_pos)
                        && tmp.Get(new_pos) != Element::Obstacle)
                        stack.push_back(make_tuple(lvl + 1, new_pos));
                }
            }
        }

        return rtn;
    }

    void ApplyPath(vector<Pos> const &path)
    {
        for (ptrdiff_t i = 1, l = path.size() - 1; i < l; ++i)
            Set(path[i], Map::Element::Path);
    }

    Element operator()(ptrdiff_t i, ptrdiff_t j) const
    {
        if (!IsValidIndex(i, j))
            throw std::out_of_range("Invalid index.");
        return Get(i, j);
    }

    void operator()(ptrdiff_t i, ptrdiff_t j, Element elem)
    {
        if (!IsValidElement(elem))
            throw std::domain_error("Invalid value of elem.");
        if (!IsValidIndex(i, j))
            throw std::out_of_range("Invalid index.");
        Set(i, j, elem);
    }

  private:
    void _ValidateInfo(Pos &starting, Pos &destination) const
    {
        Pos st = { Invalid(), Invalid() }, ds = { Invalid(), Invalid() };

        for (ptrdiff_t i = 0; i < _height; ++i)
            for (ptrdiff_t j = 0; j < _width; ++j)
            {
                auto here = Get(i, j);

                if (here == Element::Start)
                {
                    if (st.i != Invalid())
                        throw std::logic_error(
                            "Found two or more starting points.");

                    st.i = i;
                    st.j = j;
                }

                if (here == Element::Destination)
                {
                    if (ds.i != Invalid())
                        throw std::logic_error(
                            "Found two or more destinations.");

                    ds.i = i;
                    ds.j = j;
                }

                if (here == Element::Path)
                    throw std::logic_error(
                        "This map is already used for presenting path.");
            }

        if (st.i == Invalid())
            throw std::logic_error("Could not find the starting point.");

        if (ds.i == Invalid())
            throw std::logic_error("Could not find the destination.");

        starting    = st;
        destination = ds;
    }
};

ostream &operator<<(ostream &os, Map const &map)
{
    static char c_mapping[5] = { ' ', '#', 'S', 'D', '*' };

    os.put('+');
    for (ptrdiff_t j = 0, l_j = map.width() * 2 + 1; j < l_j; ++j) os.put('-');
    os.put('+');
    os.put('\n');

    for (ptrdiff_t i = 0, l_i = map.height(); i < l_i; ++i)
    {
        os.put('|');
        os.put(' ');

        for (ptrdiff_t j = 0, l_j = map.width(); j < l_j; ++j)
        {
            os.put(c_mapping[static_cast<unsigned char>(map.Get(i, j))]);
            os.put(' ');
        }

        os.put('|');
        os.put('\n');
    }

    os.put('+');
    for (ptrdiff_t j = 0, l_j = map.width() * 2 + 1; j < l_j; ++j) os.put('-');
    os.put('+');
    os.put('\n');

    return os;
}

int main()
{
    try
    {
        ifstream ifs("input.txt", ifstream::in);
        if (!ifs)
            throw std::logic_error("Cannot find input.txt.");

        ptrdiff_t height, width;
        ifs >> height >> width;

        Map map(height, width);
        for (ptrdiff_t i = 0, l_i = map.height(); i < l_i; ++i)
            for (ptrdiff_t j = 0, l_j = map.width(); j < l_j; ++j)
            {
                int new_elem;
                ifs >> new_elem;
                map(i, j, static_cast<Map::Element>(new_elem));
            }

        ifs.close();

        ofstream ofs("output.txt");

        auto      paths = map.FindPaths();
        ptrdiff_t num   = 1;
        if (paths.empty())
            cout << "Could not found any path." << endl;
        else
        {
            cout << "Found " << paths.size()
                 << (paths.size() == 1 ? " path." : " paths.") << endl;

            for (auto const &path : paths)
            {
                Map tmp(map);
                tmp.ApplyPath(path);
                ofs << num++ << '\n' << tmp << '\n';
            }
        }

        ofs.close();
        return 0;
    }
    catch (std::exception const &ex)
    {
        cout << "Exception thrown: " << ex.what() << endl;
        return 1;
    }
}