PYATNASHKI

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <array>
#include <string>
#include <cstring>
#include <algorithm>

const char FieldSize = 16;
const std::array<char, FieldSize> FinishField = { 1, 2, 3, 4,
                                                  5, 6, 7, 8,
                                                  9, 10, 11, 12,
                                                  13, 14, 15, 0 };

const std::array<char, FieldSize> NullField = { 0, 0, 0, 0,
                                                0, 0, 0, 0,
                                                0, 0, 0, 0,
                                                0, 0, 0, 0 };

class GameState
{
public:
    GameState(const std::array<char, FieldSize>& source);

    bool CanMoveUp() const;
    bool CanMoveDown() const;
    bool CanMoveLeft() const;
    bool CanMoveRight() const;

    GameState MoveUp() const;
    GameState MoveDown() const;
    GameState MoveLeft() const;
    GameState MoveRight() const;


    bool operator==(const GameState& state) const;
    friend std::ostream& operator<< (std::ostream& st, const GameState& state);
    friend struct StateHash;
    int getNullPosition() const { return nullPlace; }
    int getAt(int i) const;
    std::array<char, FieldSize> getData () const { return field; }
private:
    std::array<char, FieldSize> field;
    int nullPlace;
};

GameState::GameState( const std::array<char, FieldSize>& source) :
    field(source),
    nullPlace(-1)
{
    for (int i = 0; i < FieldSize; ++i)
        if (field[i] == 0)
            nullPlace = i;
}

bool GameState::CanMoveUp() const {
    return nullPlace < 12;
}

bool GameState::CanMoveDown() const {
    return nullPlace > 3;
}

bool GameState::CanMoveLeft() const {
    return nullPlace % 4 != 3;
}

bool GameState::CanMoveRight() const {
    return nullPlace % 4 != 0;
}

GameState GameState::MoveUp() const {
    GameState upState(*this);
    std::swap(upState.field[nullPlace], upState.field[nullPlace + 4]);
    upState.nullPlace += 4;
    return upState;
}

GameState GameState::MoveDown() const {
    GameState downState(*this);
    std::swap(downState.field[nullPlace], downState.field[nullPlace - 4]);
    downState.nullPlace -= 4;
    return downState;
}

GameState GameState::MoveLeft() const {
    GameState leftState(*this);
    std::swap(leftState.field[nullPlace], leftState.field[nullPlace + 1]);
    leftState.nullPlace++;
    return leftState;
}

GameState GameState::MoveRight() const {
    GameState rightState(*this);
    std::swap(rightState.field[nullPlace], rightState.field[nullPlace - 1]);
    rightState.nullPlace--;
    return rightState;
}

bool GameState::operator==(const GameState& state) const {
    return field == state.field;
}

std::ostream& operator<< (std::ostream& st, const GameState& state) {
    for (int row = 0; row < 4; ++row) {
        for (int col = 0; col < 4; ++col) {
            st << state.field[row*4+col] << " ";
        }
        st << "\n";
    }

    return st;
}

struct StateHash {
    size_t operator()(const GameState& state) const{
        size_t hash = 0;
        memcpy (&hash, &(state.field[0]), sizeof(hash));
        return hash;
    }
};

int GameState::getAt(int i) const {
    return field[i];
}

typedef std::pair<GameState, int> Pi;

struct Comparator
{
    bool operator()(Pi const & p1,
                    Pi const & p2)
    {
        return p1.second > p2.second;
    }
};

int countHeuristics(GameState const & pos)
{
    int res = 0;

    for (int i = 0; i < FieldSize; ++i)
    {
        unsigned char c = pos.getAt(i);
        int x = i / 4;
        int y = i % 4;
        int rx = 0;
        int ry = 0;
        if (c != 0) {
            rx = (c - 1) / 4;
            ry = (c - 1) % 4;
        }
        res += abs(x - rx) + abs(y - ry);
    }
    return res;
}


std::vector<char> Dijkstra(GameState const &start, GameState const &end)
{
    std::unordered_map<std::array<char, FieldSize>, std::pair<std::array<char, FieldSize>, char>, StateHash> p;
    std::unordered_map<std::array<char, FieldSize>, int, StateHash> d;
    std::priority_queue<Pi, std::vector<Pi>, Comparator> queue;

    queue.push(Pi(start, 0));
    d[start.getData()] = 0;
    p[start.getData()] = std::pair<std::array<char, FieldSize>, char>(start.getData(), 'N');

    while (true)
    {
        GameState const cur = queue.top().first;
        int dpth = d[queue.top().first.getData()];
        queue.pop();

        GameState empty ( NullField );
        GameState tmp = cur;

        if ( tmp.CanMoveUp() )
        {
            tmp = cur.MoveUp();
            if (p.find(tmp.getData()) == p.end()) {
                d[tmp.getData()] = dpth + 1;
                queue.push(Pi(tmp, dpth + countHeuristics(tmp)));
                p[tmp.getData()] = std::pair<std::array<char, FieldSize>, char>(cur.getData(), 'U');
                if (tmp.getData() == end.getData())
                    break;
            }
        }

        if (tmp.CanMoveDown())
        {
            tmp = cur.MoveDown();
            if (p.find(tmp.getData()) == p.end()) {
                d[tmp.getData()] = dpth + 1;
                queue.push(Pi(tmp, dpth + countHeuristics(tmp)));
                p[tmp.getData()] = std::pair<std::array<char, FieldSize>, char>(cur.getData(), 'D');
                if (tmp.getData() == end.getData())
                    break;
            }
        }

        if (tmp.CanMoveLeft())
        {
            tmp = cur.MoveLeft();
            if (p.find(tmp.getData()) == p.end()) {
                d[tmp.getData()] = dpth + 1;
                queue.push(Pi(tmp, dpth + countHeuristics(tmp)));
                p[tmp.getData()] = std::pair<std::array<char, FieldSize>, char>(cur.getData(), 'L');
                if (tmp.getData() == end.getData())
                    break;
            }
        }

        if (tmp.CanMoveRight())
        {
            tmp = cur.MoveRight();
            if (p.find(tmp.getData()) == p.end()) {
                d[tmp.getData()] = dpth + 1;
                queue.push(Pi(tmp, dpth + countHeuristics(tmp)));
                p[tmp.getData()] = std::pair<std::array<char, FieldSize>, char>(cur.getData(), 'R');
                if (tmp.getData() == end.getData())
                    break;
            }
        }
    }

    std::vector<char> parents;

    std::array<char, FieldSize> pos = end.getData();
    if (p.find(pos) == p.end())
        return parents;


    while (p[pos].second != 'N')
    {
        parents.push_back(p[pos].second);
        pos = p[pos].first;
    }
    return parents;
}

bool isPossiblePos(GameState const &pos)
{
    int inversions = 0;
    for(int i = 0; i < 16; i++)
        if (pos.getAt(i))
            for (int j = 0; j < i; ++j )
                if (pos.getAt(j) > pos.getAt(i))
                    ++inversions;

    for (int i = 0; i < 16; ++i)
        if (pos.getAt(i) == 0)
            inversions += 1 + i / 4;

    return (inversions % 2) == 1;
}


int main()
{

    std::array<char,FieldSize> s;
    int c = 0;
    for (int j = 0; j < FieldSize; ++j) {
        std::cin >> c;
        s[j] = (char)c;
    }

    GameState start(s);

    if (isPossiblePos(start)) {
        std::cout << -1;
        return 0;
    }


    GameState finish(FinishField);
    std::vector<char> l = Dijkstra(start, finish);

    std::cout << l.size() << std::endl;
    for (int i = l.size() - 1; i >= 0; --i) {
        std::cout << l[i];
    }

    return 0;
}