結果

問題 No.585 工夫のないパズル
コンテスト
ユーザー eitaho
提出日時 2017-10-27 23:46:15
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 7,682 bytes
コンパイル時間 963 ms
コンパイル使用メモリ 118,076 KB
実行使用メモリ 52,756 KB
最終ジャッジ日時 2024-11-22 02:49:00
合計ジャッジ時間 5,578 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 1 WA * 11
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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 = 2000;
    HashSet<int> Seen = new HashSet<int>();
    int GoalHash;

    public void Solve()
    {
        var Start = string.Concat(Reader.StringArray(4)).Select(c => c - 'A').ToArray();
        GoalHash = Hash(Enu.Range(0, N * N).ToArray());
        var heap = new Heap<Node>();
        heap.Push(new Node(null, false, 0, 0, 0));

        for (int turn = 0; turn < 100; turn++)
        {
            var nextHeap = new Heap<Node>();
            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<Node>();
        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<Node> 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);
                    int hash = Hash(nextGrid);
                    if (hash == GoalHash) { WriteAnswer(nextNode); return true; }
                    if (Seen.Add(hash)) heap.Push(nextNode);
                }
        return false;
    }

    void WriteAnswer(Node node)
    {
        var list = new List<string>();
        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<string>()));
    }

    int Cost(int[] grid)
    {
        int cost = 0;
        //var row = new int[N * N];
        //var col = new int[N * N];

        //for (int i = 0; i < N; i++)
        //{
        //    row[grid[i]] = i / N;
        //    col[grid[i]] = i % N;
        //}
        //for (int r = 0; r < N; r++)
        //{
        //    int sign = Math.Sign(col[r * N + 1] - col[r * N]);
        //    for (int i = 1; i < N - 1; i++)
        //        if (Math.Sign(col[r * N + i + 1] - col[r * N + i]) != sign)
        //            cost += 100;
        //}
        //for (int c = 0; c < N; c++)
        //{
        //    int sign = Math.Sign(col[c + N] - col[c]);
        //    for (int i = 1; i < N - 1; i++)
        //        if (Math.Sign(col[(i + 1) * N + c] - col[i * N + c]) != sign)
        //            cost += 100;
        //}
        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<Node>
{
    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<T>
{
    const int InitialSize = 1000;
    readonly bool greater;
    readonly Comparer<T> cmp = Comparer<T>.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<T>(int N, Func<T> 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;
    }
}
0