using System; using System.IO; using System.Linq; using System.Text; using System.Collections.Generic; using System.Diagnostics; using Enu = System.Linq.Enumerable; public class Program { static readonly int N = 4; static readonly int BeamWidth = 1000; HashSet Seen = new HashSet(); Random random = new Random(0); public void Solve() { var Start = string.Concat(Reader.StringArray(4)).Select(c => c - 'A').ToArray(); var heap = new Heap(); heap.Push(new Node(null, false, 0, 0, 0)); for (int turn = 0; turn < 100; turn++) { var nextHeap = new Heap(); for (int w = 0; heap.Count > 0 && w < BeamWidth; w++) { var node = heap.Pop(); var grid = GetGrid(Start, node); if (PushAll(grid, node, nextHeap)) { Console.ReadLine(); return; } } heap = nextHeap; } Console.WriteLine("nooo"); Console.ReadLine(); } int[] GetGrid(int[] Start, Node node) { var grid = new int[N * N]; Array.Copy(Start, grid, Start.Length); var list = new List(); for (var n = node; n != null; n = n.Parent) list.Add(n); for (int i = list.Count - 1; i >= 0; i--) if (list[i].IsRow) RotateRow(grid, list[i].Index, list[i].Steps); else RotateCol(grid, list[i].Index, list[i].Steps); return grid; } void RotateRow(int[] grid, int r, int steps) { var curr = new int[N]; for (int i = 0; i < N; i++) curr[i] = grid[r * N + i]; for (int i = 0; i < N; i++) grid[r * N + (i + steps) % N] = curr[i]; } void RotateCol(int[] grid, int c, int steps) { var curr = new int[N]; for (int i = 0; i < N; i++) curr[i] = grid[i * N + c]; for (int i = 0; i < N; i++) grid[((i + steps) % N) * N + c] = curr[i]; } int Hash(int[] grid) { int hash = 0; foreach (int a in grid) hash = hash * (N * N) + a; return hash; } bool PushAll(int[] grid, Node node, Heap heap) { for (int index = 0; index < N; index++) for (int steps = 1; steps < N; steps++) for (int isRow = 0; isRow < 2; isRow++) { var nextGrid = new int[N * N]; Array.Copy(grid, nextGrid, grid.Length); if (isRow == 1) RotateRow(nextGrid, index, steps); else RotateCol(nextGrid, index, steps); int cost = Cost(nextGrid); var nextNode = new Node(node, isRow == 1, index, steps, cost); if (Goal(nextGrid)) { WriteAnswer(nextNode); return true; } if (Seen.Add(Hash(nextGrid))) heap.Push(nextNode); } return false; } bool Goal(int[] grid) { for (int i = 0; i < N * N; i++) if (grid[i] != i) return false; return true; } void WriteAnswer(Node node) { var list = new List(); for (var n = node; n.Parent != null; n = n.Parent) list.Add((n.IsRow ? "R" : "C") + " " + n.Index + " " + n.Steps); Console.WriteLine(list.Count + "\n" + string.Join("\n", list.Reverse())); } int Cost(int[] grid) { int cost = 0; for (int r = 0; r < N; r++) for (int c = 0; c < N; c++) { int x = grid[r * N + c]; int gr = x / N, gc = x % N; cost += Math.Abs(gr - r) + Math.Abs(gc - c); } return cost; } } class Node : IComparable { public Node Parent; public bool IsRow; public int Index; public int Steps; public int Cost; public Node(Node parent, bool isRow, int index, int steps, int cost) { Parent = parent; IsRow = isRow; Index = index; Steps = steps; Cost = cost; } public int CompareTo(Node other) { return Cost - other.Cost; } } public class Heap { const int InitialSize = 1000; readonly bool greater; readonly Comparer cmp = Comparer.Default; T[] A = new T[InitialSize]; public int Count { get; private set; } public Heap(bool greater = false) { this.greater = greater; } public T Peek() { return A[1]; } bool Cmp(T a, T b) { if (greater) return cmp.Compare(a, b) > 0; return cmp.Compare(a, b) < 0; } public void Push(T val) { int i = ++Count; if (i == A.Length) Array.Resize(ref A, A.Length * 2); for (; i > 1 && Cmp(val, A[i >> 1]); i >>= 1) A[i] = A[i >> 1]; A[i] = val; } public T Pop() { T res = A[1], val = A[Count--]; if (Count == 0) return res; int i = 1; for (int L = i << 1; L <= Count; L = i << 1) { if (L + 1 <= Count && Cmp(A[L + 1], A[L])) L++; if (Cmp(A[L], val)) { A[i] = A[L]; i = L; } else break; } A[i] = val; return res; } } class Entry { static void Main() { new Program().Solve(); } } class Reader { static TextReader reader = Console.In; static readonly char[] separator = { ' ' }; static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries; static string[] A = new string[0]; static int i; static void Init() { Dispose(); A = new string[0]; } public static void Set(TextReader r) { Init(); reader = r; } public static void Set(string file) { Init(); reader = new StreamReader(file); } public static bool HasNext() { return CheckNext(); } public static string String() { return Next(); } public static int Int() { return int.Parse(Next()); } public static long Long() { return long.Parse(Next()); } public static double Double() { return double.Parse(Next()); } public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); } public static int[] IntArray(int N) { return Range(N, Int); } public static int[][] IntTable(int H) { return Range(H, IntLine); } public static string[] StringArray(int N) { return Range(N, Next); } public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); } public static string Line() { return reader.ReadLine().Trim(); } public static T[] Range(int N, Func f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; } public static void Dispose() { reader.Dispose(); } static string[] Split(string s) { return s.Split(separator, op); } static string Next() { CheckNext(); return A[i++]; } static bool CheckNext() { if (i < A.Length) return true; string line = reader.ReadLine(); if (line == null) return false; if (line == "") return CheckNext(); A = Split(line); i = 0; return true; } }