結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2024-12-20 03:34:14
言語 Ruby
(3.4.1)
結果
AC  
実行時間 1,383 ms / 2,000 ms
コード長 1,725 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2024-12-20 03:34:37
合計ジャッジ時間 22,117 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

class PPuzzle
	attr_reader :n
	def initialize(n,icol=[],irow=[],matrix=[])
		@n = n
		@icol = icol
		@irow = irow
		@matrix = matrix
	end
	def read()
		@icol = @n.times.to_a
		@irow = @n.times.to_a
		@matrix = @n.times.map{gets.chomp.split.map{|s|s.to_i-1}}
		self
	end
	def clone()
		PPuzzle.new(@n,@icol.dup,@irow.dup,@matrix)
	end
	def at(r,c)
		@matrix[@irow[r]][@icol[c]]
	end
	def select_col(x)
		@n.times.map{|r|self.at(r,x)}
	end
	def select_row(y)
		@n.times.map{|c|self.at(y,c)}
	end
	def operate_col(x)
		pa = self.select_col(x)
		t = @icol.dup
		@n.times{|i| @icol[pa[i]] = t[i] }
	end
	def operate_row(y)
		pa = self.select_row(y)
		t = @irow.dup
		@n.times{|i| @irow[pa[i]] = t[i] }
	end
	def ==(other)
		@n.times.all?{|r| @n.times.all?{|c| self.at(r,c)==other.at(r,c) }}
	end
end

def search(b,k,t,v)
	return t==b if k==0
	for i in b.select_col(0)
		v.push(i)
		s = t.clone
		s.operate_col(i)
		return true if search(b,k-1,s,v)
		v.pop
		v.push(i+b.n)
		s = t.clone
		s.operate_row(i)
		return true if search(b,k-1,s,v)
		v.pop
	end
	false
end

def cycle(p)
	t=[0]*p.size
	w=p.dup
	loop.with_index(1) {|_,cnt|
		p.size.times{|i| t[p[i]] = w[i] }
		break cnt if t == p
		t,w = [w,t]
	}
end

def solve(n,k,a,b)
	ops = []
	search(b,k,a,ops)
	s=a.clone
	ans = []
	ops.each{|op|
		if op<n
			pa = s.select_col(op)
			s.operate_col(op)
		else
			pa = s.select_row(op-n)
			s.operate_row(op-n)
		end
		z = op % n
		tmp = []
		cycle(pa).pred.times {
			z = pa[z]
			tmp.push(op<n ? z : (z+n))
		}
		ans = tmp+ans
	}
	ans
end

n, k = gets.chomp.split.map{|s|s.to_i}
a = PPuzzle.new(n).read()
b = PPuzzle.new(n).read()
ans = solve(n,k,a,b)
puts ans.size
puts ans.map{|op| op<n ? "C %d"%(op+1) : "R %d"%(op+1-n) }*"\n"
0