結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2024-12-20 20:33:52
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 614 ms / 2,000 ms
コード長 3,415 bytes
コンパイル時間 8,093 ms
コンパイル使用メモリ 167,664 KB
実行使用メモリ 214,236 KB
最終ジャッジ日時 2024-12-20 20:34:12
合計ジャッジ時間 17,929 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (127 ms)。
MSBuild のバージョン 17.9.6+a4ecab324 (.NET)
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff #
プレゼンテーションモードにする

using System;
using System.Collections.Generic;
using System.Linq;
public class Solver
{
    static List<int> Solve(int n, int k, int[,] a, int[,] b)
    {
        var ops = new List<int>();
        Search(b, k, a, ops);
        ops.Reverse();
        
        var ans = new List<int>();
        var s = (int[,])a.Clone();
        foreach (var op in ops)
        {
            List<int> p;
            if (op < n)
            {
                p = SelectCol(s, op);
                ReorderColsByColPerm(s, op);
            }
            else
            {
                p = SelectRow(s, op-n);
                ReorderRowsByRowPerm(s, op-n);
            }
            var z = op%n;
            var tmp = new List<int>();
            for (var cnt = cycle(p)-1; cnt > 0; cnt--)
            {
                z = p[z];
                tmp.Add(op < n ? z : (z+n));
            }
            ans = tmp.Concat(ans).ToList();
        }
        return ans;
    }
    
    static bool Search(int[,] b, int k, int[,] t, List<int> v)
    {
        if (k == 0)
        {
            return IsSame(b, t);
        }
        for (var i = 0; i <= b.GetUpperBound(0); i++)
        {
            v.Insert(0, i);
            var s = (int[,])t.Clone();
            ReorderColsByColPerm(s, i);
            if (Search(b, k-1, s, v)) {
                return true;
            }
            v[0] += b.GetUpperBound(0)+1;
            s = (int[,])t.Clone();
            ReorderRowsByRowPerm(s, i);
            if (Search(b, k-1, s, v)) {
                return true;
            }
            v.RemoveAt(0);
        }
        return false;
    }
    
    static int cycle(List<int> p)
    {
        var t = new int[p.Count];
        var w = p.ToArray();
        for (var cnt = 1; ; cnt++)
        {
            for (var i = 0; i < p.Count; i++)
            {
                t[p[i]] = w[i];
            }
            var ok = true;
            for (var i = 0; i < p.Count; i++)
            {
                if (t[i] != p[i])
                {
                    ok = false;
                }
            }
            if (ok)
            {
                return cnt;
            }
            var tmp = t; t = w; w = tmp;
        }
    }
    
    static void ReorderColsByColPerm(int[,] s, int x)
    {
        var p = SelectCol(s, x);
        var t = (int[,])s.Clone();
        for (var r = 0; r <= s.GetUpperBound(0); r++)
        {
            for (var c = 0; c <= s.GetUpperBound(1); c++)
            {
                s[ r, t[c, x] ] = t[r, c];
            }
        }
    }
    static void ReorderRowsByRowPerm(int[,] s, int y)
    {
        var p = SelectRow(s, y);
        var t = (int[,])s.Clone();
        for (var r = 0; r <= s.GetUpperBound(0); r++)
        {
            for (var c = 0; c <= s.GetUpperBound(1); c++)
            {
                s[ t[y, r], c ] = t[r, c];
            }
        }
    }
    
    static List<int> SelectCol(int[,] s, int x)
    {
        var v = new List<int>();
        for (var r = 0; r <= s.GetUpperBound(0); r++)
        {
            v.Add(s[r,x]);
        }
        return v;
    }
    static List<int> SelectRow(int[,] s, int y)
    {
        var v = new List<int>();
        for (var c = 0; c <= s.GetUpperBound(1); c++)
        {
            v.Add(s[y,c]);
        }
        return v;
    }
    
    static bool IsSame(int[,] s, int[,] t)
    {
        for (var r = 0; r <= s.GetUpperBound(0); r++)
        {
            for (var c = 0; c <= s.GetUpperBound(1); c++)
            {
                if (s[r,c] != t[r,c])
                {
                    return false;
                }
            }
        }
        return true;
    }
    
    public static void Main()
    {
        var input = ReadAll();
        var n = input.Dequeue();
        var k = input.Dequeue();
        var a = new int[n,n];
        var b = new int[n,n];
        for (var r = 0; r < n; r++)
        {
            for (var c = 0; c < n; c++)
            {
                a[r,c] = input.Dequeue() - 1;
            }
        }
        for (var r = 0; r < n; r++)
        {
            for (var c = 0; c < n; c++)
            {
                b[r,c] = input.Dequeue() - 1;
            }
        }
        
        var ans = Solve(n, k, a, b);
        
        Console.Out.WriteLine(ans.Count);
        foreach (var op in ans)
        {
            if (op < n)
            {
                Console.Out.WriteLine("C {0}", op+1);
            }
            else
            {
                Console.Out.WriteLine("R {0}", op+1-n);
            }
        }
        
    }
    
    static Queue<int> ReadAll()
    {
        return new Queue<int>(Console.In.ReadToEnd().Trim()
            .Split(null).Select(s => Convert.ToInt32(s)));
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0