yipo
11/7/2017 - 4:12 PM

uva10284

Chessboard in FEN

#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
struct point
{
public:
    point(const T &x, const T &y) : x(x), y(y)
    {
    }

    point rotate(size_t times) const
    {
        switch (times % 4)
        {
        case 0:
            return point(+x, +y);
        case 1:
            return point(-y, +x);
        case 2:
            return point(-x, -y);
        case 3:
            return point(+y, -x);
        }
        return point(0, 0);
    }

    bool operator <(const point &rhs) const
    {
        return (x != rhs.x) ? (x < rhs.x) : (y < rhs.y);
    }

    point &operator +=(const point &rhs)
    {
        x += rhs.x, y += rhs.y;
        return *this;
    }

public:
    T x, y;
};

template <typename T>
class matrix
{
public:
    matrix(size_t size, const T &value = T()) : m_matrix(size*size, value), m_size(size)
    {
    }

    size_t size() const
    {
        return m_size;
    }

    const T &at(size_t x, size_t y) const
    {
        check_range(x, y);
        return m_matrix.at(x + m_size*y);
    }

    T &at(size_t x, size_t y)
    {
        check_range(x, y);
        return m_matrix.at(x + m_size*y);
    }

    bool test_range(size_t x, size_t y) const
    {
        return x < m_size && y < m_size;
    }

    size_t count(const T &value) const
    {
        return ::count(m_matrix.begin(), m_matrix.end(), value);
    }

private:
    void check_range(size_t x, size_t y) const
    {
        if (!test_range(x, y)) throw out_of_range("out of range");
    }

private:
    vector<T> m_matrix;
    size_t m_size;
};

template <typename T>
set<T> operator +(const set<T> &lhs, const set<T> &rhs)
{
    set<T> result = lhs;
    result.insert(rhs.begin(), rhs.end());
    return result;
}

class chess
{
public:
    static size_t count_not_attacked(const string &description)
    {
        matrix<char> chessboard = parse_fen_description(description);

        for (size_t y = 0; y < chessboard.size(); y++)
        {
            for (size_t x = 0; x < chessboard.size(); x++)
            {
                if (isalpha(chessboard.at(x, y))) attack(chessboard, x, y);
            }
        }

        return chessboard.count(0);
    }

private:
    using point = ::point<int>;

    class movement
    {
    public:
        movement(const set<point> &directions, bool extend) : m_directions(directions), m_extend(extend)
        {
        }

        const set<point> &get_directions() const
        {
            return m_directions;
        }

        bool is_extend() const
        {
            return m_extend;
        }

    private:
        set<point> m_directions;
        bool m_extend;
    };

private:
    static matrix<char> parse_fen_description(const string &description)
    {
        matrix<char> chessboard(8, 0);

        istringstream iss(description);
        string line;

        size_t y = 0;
        while (getline(iss, line, '/'))
        {
            size_t x = 0;
            for (const auto ch : line)
            {
                if (isdigit(ch))
                {
                    x += (ch - '0');
                    continue;
                }

                try
                {
                    chessboard.at(x, y) = ch;
                    x++;
                }
                catch (...)
                {
                    throw invalid_argument("syntax error");
                }
            }
            y++;
        }

        return chessboard;
    }

    static set<point> make_symmetry(const set<point> &directions)
    {
        set<point> result;
        for (const auto d : directions)
        {
            for (size_t i = 0; i < 4; i++) result.insert(d.rotate(i));
        }
        return result;
    }

    static map<char, movement> get_game_rules()
    {
        auto cross = make_symmetry({ point(1, 0) });
        auto diagonal = make_symmetry({ point(1, 1) });
        auto any = cross + diagonal;

        return
        {
            { 'k', movement(any, false) },
            { 'K', movement(any, false) },
            { 'q', movement(any, true) },
            { 'Q', movement(any, true) },
            { 'r', movement(cross, true) },
            { 'R', movement(cross, true) },
            { 'b', movement(diagonal, true) },
            { 'B', movement(diagonal, true) },
            { 'n', movement(make_symmetry({ point(+1, +2), point(+2, +1) }), false) },
            { 'N', movement(make_symmetry({ point(+1, +2), point(+2, +1) }), false) },
            { 'p', movement({ point(+1, +1), point(-1, +1) }, false) },
            { 'P', movement({ point(+1, -1), point(-1, -1) }, false) },
        };
    }

    static void attack(matrix<char> &chessboard, size_t x, size_t y)
    {
        static const auto rules = get_game_rules();

        const auto &move = rules.at(chessboard.at(x, y));
        for (const auto d : move.get_directions())
        {
            try
            {
                point p(x, y);
                do
                {
                    p += d;
                    if (!chessboard.test_range(p.x, p.y)) break;
                    auto &there = chessboard.at(p.x, p.y);
                    if (isalpha(there)) break;
                    there = 1;
                }
                while (move.is_extend());
            }
            catch (const out_of_range &)
            {
            }
        }
    }
};

int main()
{
    string description;
    while (cin >> description)
    {
        cout << chess::count_not_attacked(description) << endl;
    }
    return 0;
}