結果

問題 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)));
	}
}
0