#include <array>
#include <iostream>
#include <functional>
#include <string>
#include <utility>
#include <vector>

#include <cctype>
#include <cstring>

#include "exprtk.hpp"


using expr_t = exprtk::expression<float>;
using parser_t = exprtk::parser<float>;


template<size_t N, size_t M>
struct usage_matrix : std::array<bool, N*M> {
    usage_matrix() {
        memset(this, 0, sizeof(*this));
    }
    usage_matrix(const usage_matrix&) = default;
    usage_matrix(usage_matrix&&) = default;
    usage_matrix& operator=(const usage_matrix&) = default;
    usage_matrix& operator=(usage_matrix&&) = default;

    decltype(auto) operator()(size_t i, size_t j) const {
        return (*this)[i*M + j];
    }
    decltype(auto) operator()(size_t i, size_t j) {
        return (*this)[i*M + j];
    }
};

template<size_t N, size_t M, typename P>
usage_matrix<N, M> to_usage_matrix(const char* field, P&& predicate)
{
    usage_matrix<N, M> ret;

    for (unsigned i = 0; i < N; i++)
        for (unsigned j = 0; j < M; j++)
            ret(i, j) = predicate(field[i*M + j]);

    return ret;
}


class move {
public:
    enum enam : char {
        U, UR,
        R, DR,
        D, DL,
        L, UL,
    };
};

const char* move_to_arrow[] = {
    "↑", "↗",
    "→", "↘",
    "↓", "↙",
    "←", "↖",
};

using seq_of_moves = std::vector<move::enam>;

std::ostream& operator<<(std::ostream& os, const seq_of_moves& moves)
{
    for (auto move : moves)
        os << move_to_arrow[move];

    return os;
}

const std::pair<int, int> move_to_dxdy[] = {
    { -1,  0 }, // up
    { -1, +1 }, // up-right
    {  0, +1 }, // right
    { +1, +1 }, // down-right
    { +1,  0 }, // down
    { +1, -1 }, // down-left
    {  0, -1 }, // left
    { -1, -1 }, // up-left
};

std::pair<int, int> operator+(std::pair<int, int> x, std::pair<int, int> dx)
{
    return { x.first + dx.first, x.second + dx.second };
}

template<size_t N, size_t M>
bool is_move_possible(usage_matrix<N, M>& matrix, std::pair<int, int> cur_pos, std::pair<int, int> dxdy)
{
    std::pair<int, int> upd_pos = cur_pos + dxdy;
    int i = upd_pos.first;
    int j = upd_pos.second;

    if (i < 0 || size_t(i) >= N)
        return false;

    if (j < 0 || size_t(j) >= M)
        return false;

    return matrix(i, j) == 0;
}

template<size_t N, size_t M>
unsigned char get_possible_moves(usage_matrix<N, M>& matrix, std::pair<int, int> cur_pos)
{
    unsigned char ret = 0;
    for (int i = 0; i < 8; i++) {
        ret |= is_move_possible(matrix, cur_pos, move_to_dxdy[i]) << i;
    }
    return ret;
}

parser_t parser;
expr_t expression;

template<size_t N, size_t M>
void find_solutions(usage_matrix<N, M> digits, usage_matrix<N, M> signs,
                    std::pair<int, int> cur_pos,
                    const char* fld, std::string expr, size_t sol_length,
                    seq_of_moves moves, std::vector<seq_of_moves>& out)
{
    if (expr.length() == sol_length) {
        parser.compile(expr, expression);
        if (expression.value() == 0) {
            std::cout << expr << '\t' << moves << '\n';
            out.push_back(std::move(moves));
        }
        return;
    }

    unsigned char sign_moves = get_possible_moves(signs, cur_pos);
    for (int i = 0; i < 8; i++) {
        if (((sign_moves >> i) & 1) == 0)
            continue;

        auto upd_pos_1 = cur_pos + move_to_dxdy[i];
        auto upd_signs = signs;
        auto upd_expr_1 = expr;
        auto upd_moves_1 = moves;

        upd_signs(upd_pos_1.first, upd_pos_1.second) = 1;
        upd_expr_1 += fld[upd_pos_1.first * M + upd_pos_1.second];
        upd_moves_1.push_back(move::enam(i));

        unsigned char digit_moves = get_possible_moves(digits, upd_pos_1);
        for (int j = 0; j < 8; j++) {
            if (((digit_moves >> j) & 1) == 0)
                continue;

            auto upd_pos_2 = upd_pos_1 + move_to_dxdy[j];
            auto upd_digits = digits;
            auto upd_expr_2 = upd_expr_1;
            auto upd_moves_2 = upd_moves_1;

            upd_digits(upd_pos_2.first, upd_pos_2.second) = 1;
            upd_expr_2 += fld[upd_pos_2.first * M + upd_pos_2.second];
            upd_moves_2.push_back(move::enam(j));

            find_solutions(std::move(upd_digits), std::move(upd_signs),
                           upd_pos_2,
                           fld, std::move(upd_expr_2), sol_length,
                           std::move(upd_moves_2), out);
        }
    }
}


#ifndef __TEST__

int main(int argc, char* argv[])
{

    const int width = 4;
    const int height = 6;
    const char* field =
        "1+5-"
        "2-7+"
        "3+3*"
        "4+2-"
        "2-4+"
        "62-4"
    ;

    auto initial_digits = to_usage_matrix<height, width>(field, [](auto c) {
        return !isdigit(c);
    });
    auto initial_signs  = to_usage_matrix<height, width>(field, [](auto c) {
        return isdigit(c);
    });
    initial_digits(0, 0) = 1;
    initial_digits(0, 2) = 1;

    std::pair<int, int> initial_pos = {0, 0};
    std::string initial_expr = "1";
    const int solution_length = 11;
    seq_of_moves initial_moves = { };

    std::vector<seq_of_moves> solutions;

    find_solutions(std::move(initial_digits), std::move(initial_signs),
                   initial_pos,
                   field, std::move(initial_expr), solution_length,
                   std::move(initial_moves), solutions);

    std::cout << solutions.size() << '\n';
}

#else

#define CATCH_CONFIG_MAIN
#include "catch.hpp"

TEST_CASE("Test is_move_possible", "[is_move_possible]") {
    usage_matrix<2, 2> matrix_1;

    REQUIRE( is_move_possible(matrix_1, {0, 0}, { -1,  0 }) == false );
    REQUIRE( is_move_possible(matrix_1, {0, 0}, { -1, -1 }) == false );
    REQUIRE( is_move_possible(matrix_1, {0, 0}, { +1, +1 }) == true );
    REQUIRE( is_move_possible(matrix_1, {0, 0}, {  0, +1 }) == true );
    REQUIRE( is_move_possible(matrix_1, {1, 1}, { -1,  0 }) == true );
    REQUIRE( is_move_possible(matrix_1, {1, 1}, { -1, -1 }) == true );
    REQUIRE( is_move_possible(matrix_1, {1, 1}, { +1, +1 }) == false );
    REQUIRE( is_move_possible(matrix_1, {1, 1}, {  0, +1 }) == false );
}

TEST_CASE("Test get_possible_moves", "[get_possible_moves]") {
    usage_matrix<2, 2> matrix_1;

    REQUIRE( get_possible_moves(matrix_1, {0, 0}) == (1 << move::R) + (1 << move::DR) + (1 << move::D) );
    REQUIRE( get_possible_moves(matrix_1, {0, 1}) == (1 << move::L) + (1 << move::DL) + (1 << move::D) );
    REQUIRE( get_possible_moves(matrix_1, {1, 0}) == (1 << move::R) + (1 << move::UR) + (1 << move::U) );
    REQUIRE( get_possible_moves(matrix_1, {1, 1}) == (1 << move::L) + (1 << move::UL) + (1 << move::U) );

    matrix_1(0, 0) = 1;

    REQUIRE( get_possible_moves(matrix_1, {1, 1}) == (1 << move::L) + (0 << move::UL) + (1 << move::U) );

    usage_matrix<3, 3> matrix_2;

    REQUIRE( get_possible_moves(matrix_2, {1, 1}) == 0xff );
}

#endif