#212284 (C#(csc)) No.585 工夫のないパズル

提出ソース

結果

問題	No.585 工夫のないパズル
ユーザー	eitaho
提出日時	2017-10-27 23:34:42
言語	C#(csc) (csc 3.9.0)
結果	TLE
実行時間	-
コード長	6,729 bytes
コンパイル時間	2,529 ms
コンパイル使用メモリ	118,484 KB
実行使用メモリ	93,140 KB
最終ジャッジ日時	2024-11-22 02:48:14
合計ジャッジ時間	31,429 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	36 ms 25,472 KB
testcase_01	AC	37 ms 20,608 KB
testcase_02	AC	497 ms 41,216 KB
testcase_03	TLE	-
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	AC	239 ms 36,096 KB
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	AC	108 ms 93,140 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

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

    public void Solve()
    {
        var Start = string.Concat(Reader.StringArray(4)).Select(c => c - 'A').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)) return;
            }
            heap = nextHeap;
        }

        Console.WriteLine("nooo");
    }

    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);
                    if (cost == 0) { WriteAnswer(nextNode); return true; }
                    if (Seen.Add(Hash(nextGrid))) 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[] A)
    {
        int res = 0;
        for (int r = 0; r < N; r++)
            for (int c = 0; c < N; c++)
            {
                int x = A[r * N + c];
                int gr = x / N, gc = x % N;
                res += Math.Abs(gr - r) + Math.Abs(gc - c);
            }
        return res;
    }
}

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;
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード