---

using Microsoft.VisualBasic.CompilerServices;
using System;
using System.Data;
using System.Diagnostics;
using System.Security.Authentication;

namespace Pyatnashki
{
    class Program
    {
        static readonly int[] dx = new int[4] { 0, -1, 0, 1 };
        static readonly int[] dy = new int[4] { 1, 0, -1, 0 };
        static readonly char[] move_desc = new char[4] { 'D', 'L', 'U', 'R' };
        static readonly int[] oppositive_move = new int[4] { 2, 3, 0, 1 };

        const int infinity = 10000;
        static int x0;
        static int y0;
        static int[] goalX = new int[16];
        static int[] goalY = new int[16];
        static int[,] board = new int[4, 4];
        static int step;

        static int[,] boardGoal = new int[4, 4];

        static int minPrevIteration, deepness;
        static string result = "";

        static void initGoalArrays()
        {
            for (int i = 0; i <= 14; i++)
            {
                goalX[i + 1] = i % 4;
                goalY[i + 1] = i / 4;
            }
            goalX[0] = 4;
            goalY[0] = 4;
        }

        static void swap(int y1, int x1, int y2, int x2)
        {
            int value1, value2;
            value1 = board[y1, x1];
            value2 = board[y2, x2];
            board[y1, x1] = value2;
            board[y2, x2] = value1;
        }

        static bool isSolvable()
        {
            int count = 0;
            int transpos = 0;
            int value = 0;
            int[] a = new int [17];

            for (int i = 0; i <= 3; i++)
            {
                if (i % 2 == 0)
                {
                    for (int j = 0; j <= 3; j++)
                    {
                        value = board[i, j];
                        if (value > 0)
                        {
                            a[count] = value;
                            count++;
                        }
                    }
                }
                else
                {
                    for (int j = 3; j >= 0; j--)
                    {
                        value = board[i, j];
                        if (value > 0)
                        {
                            a[count] = value;
                            count++;
                        }
                    }
                }
            }
            for (int i = 0; i <= count - 2; i++)
            {
                for (int j = i + 1 ; j <= count - 1; j++)
                {
                    if (a[i] > a[j])
                    {
                        transpos++;
                    }
                }
            }
            if(transpos % 2 == 1)
            {
                return true;
            }
            return false;
        }

        static int estimate()
        {
            int manhattan = 0;
            int value, m;
            for (int i = 0; i <= 3; i++)
            {
                for (int j = 0; j <= 3; j++)
                {
                    value = board[i, j];
                    if ((value > 0) && (value != boardGoal[i,j]))
                    {
                        m = Math.Abs(i - goalY[value]) + Math.Abs(j - goalX[value]);
                        manhattan += m;
                    }
                }
            }
            return manhattan;
        }

        static bool recSearch(int g, int previousMove, int x0, int y0)
        {
            int h = estimate();
            if (h == 0)
            {
                return true;
            }
            int f = g + h;
            if( f > deepness)
            {
                if (minPrevIteration > f) minPrevIteration = f;
                return false;
            }
            int newx, newy;
            bool res;
            for (int i = 0; i <= 3; i++)
            {
                if(oppositive_move[i] != previousMove)
                {
                    newx = x0 + dx[i];
                    newy = y0 + dy[i];
                    if ((newy <= 3) && (newy >= 0) && (newx <= 3) && (newx >= 0))
                    {
                        swap(y0, x0, newy, newx);
                        res = recSearch(g + 1, i, newx, newy);
                        swap(y0, x0, newy, newx);
                        if (res)
                        {
                            result = move_desc[i] + result;
                            step++;
                            return true;
                        }
                    }
                }
            }
            return false;
        }

        static bool idaStar()
        {

            bool res = false;
            deepness = estimate();
            while (deepness <= 50)
            {
                minPrevIteration = infinity;
                for (int i = 0; i <= 3; i++)
                {
                    for (int j = 0; j <= 3; j++)
                    {
                        if(board[i,j] == 0)
                        {
                            x0 = j;
                            y0 = i;
                        }
                    }
                }
                step = 0;
                res = recSearch(0, -1, x0, y0);
                deepness = minPrevIteration;
                if (res) break;
            }
            return res;
        }
        static void Main(string[] args)
        {
            initGoalArrays();
            // Исходная доска
            board[0,0] = 2;
            board[0,1] = 5;
            board[0,2] = 4;
            board[0,3] = 6;

            board[1,0] = 1;
            board[1,1] = 13;
            board[1,2] = 11;
            board[1,3] = 3;

            board[2,0] = 14;
            board[2,1] = 12;
            board[2,2] = 7;
            board[2,3] = 10;

            board[3,0] = 8;
            board[3,1] = 15;
            board[3,2] = 9;
            board[3,3] = 0;

            // Целевая доска
            boardGoal[0,0] = 1;
            boardGoal[0,1] = 2;
            boardGoal[0,2] = 3;
            boardGoal[0,3] = 4;

            boardGoal[1,0] = 5;
            boardGoal[1,1] = 6;
            boardGoal[1,2] = 7;
            boardGoal[1,3] = 8;

            boardGoal[2,0] = 9;
            boardGoal[2,1] = 10;
            boardGoal[2,2] = 11;
            boardGoal[2,3] = 12;

            boardGoal[3,0] = 13;
            boardGoal[3,1] = 14;
            boardGoal[3,2] = 15;
            boardGoal[3,3] = 0;

            if (!isSolvable())
            {
                Console.WriteLine("Задача неразрешима");
            }
            else if ( estimate() == 0)
            {
                Console.WriteLine("Это уже цель");
            }
            else if (idaStar())
            {
                Console.WriteLine($"Количество ходов: {step}");
                Console.WriteLine($"Путь: {result}");
            }
            else
            {
                Console.WriteLine("IDA* failed");
            }
        }
    }
}