結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2024-12-31 16:20:37
言語 Scala(Beta)
(3.6.2)
結果
AC  
実行時間 1,724 ms / 2,000 ms
コード長 1,955 bytes
コンパイル時間 11,923 ms
コンパイル使用メモリ 273,564 KB
実行使用メモリ 78,396 KB
最終ジャッジ日時 2024-12-31 16:22:15
合計ジャッジ時間 68,987 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import scala.io.StdIn.readLine

type Matrix = Array[Array[Int]] 

def reorderColsByColPerm(s: Matrix, x: Int) =
	val n = s.length
	val t = s.map(_.clone).toArray
	for r <- 0 until n do
		for c <- 0 until n do
			s( r )( t(c)(x) ) = t(r)(c)

def reorderRowsByRowPerm(s: Matrix, y: Int) =
	val n = s.length
	val t = s.map(_.clone).toArray
	for r <- 0 until n do
		for c <- 0 until n do
			s( t(y)(r) )( c ) = t(r)(c)

def selectCol(s: Matrix, x: Int): Array[Int] =
	s.map(_(x)).toArray
	
def selectRow(s: Matrix, y: Int): Array[Int] =
	s(y).clone

def isSame(a: Matrix, b: Matrix): Boolean =
	a.corresponds(b)(_.sameElements(_))

def search(b: Matrix, k: Int, t: Matrix, ops: Array[Int]): Boolean =
	if k == 0 then
		return isSame(b, t)
	else
		val n = b.length
		for op <- 0 until 2*n do
			ops(ops.length-k) = op
			val s = t.map(_.clone).toArray
			if op < n then
				reorderColsByColPerm(s,op)
			else
				reorderRowsByRowPerm(s,op-n)
			if search(b, k-1, s, ops) then
				return true
		return false

def solve(n: Int, k: Int, a: Matrix, b: Matrix): List[Int] =
	val ops = new Array[Int](k)
	search(b, k, a, ops)
	
	var ans = List[Int]()
	for op <- ops do
		val p = if op < n then selectCol(a,op) else selectRow(a,op-n)
		var z = op % n
		var tmp = List[Int]()
		var t = (0 until n).toArray
		var w = p.clone
		while !p.sameElements(t) do
			z = p(z)
			tmp = (if op < n then z else (z+n)) :: tmp
			for i <- 0 until n do t(p(i)) = w(i)
			w = t.clone
		ans = tmp.tail.reverse ::: ans
		if op < n then
			reorderColsByColPerm(a,op)
		else
			reorderRowsByRowPerm(a,op-n)
	return ans

def readInts() = readLine().split(" ").map(_.toInt-1)

@main def main() =
	val Array(n,k) = readInts().map(_+1)
	val a: Matrix = (1 to n).map(_ => readInts()).toArray
	val b: Matrix = (1 to n).map(_ => readInts()).toArray
	
	val ans = solve(n,k,a,b)
	
	println(ans.length)
	for op <- ans do
		if op < n then
			println("C " + (op+1))
		else
			println("R " + (op+1-n))
0