/// <reference path="/home/linuxbrew/.linuxbrew/lib/node_modules/@types/node/globals.d.ts" /> require('fs').readFile('/dev/stdin', 'utf-8', (err, data) => run(data)); function run(data: string): void { const input = data.split(/\s+/).map(s => parseInt(s)); const n = input.shift(); const k = input.shift(); const a = new PPuzzle(n).scan(input); const b = new PPuzzle(n).scan(input); const ans = solve(n, k, a, b); console.log(ans.length); ans.map( op => op < n ? `C ${op+1}` : `R ${op+1-n}` ) .forEach( s => console.log(s) ); } function solve(n: number, k: number, a: PPuzzle, b: PPuzzle): number[] { const ops: number[] = []; search(b, k, a, ops); let ans: number[] = []; let s = a.clone(); ops.forEach( op => { let p; if (op < n) { p = s.selectCol(op); s.operateCol(op); } else { p = s.selectRow(op-n); s.operateRow(op-n); } const tmp = []; let z = op % n; for (let cnt = cycle(p)-1; cnt > 0; cnt--) { z = p[z]; tmp.push(op < n ? z : (z+n)); } ans = tmp.concat(ans); }); return ans; } function search(b: PPuzzle, k: number, t: PPuzzle, v: number[]): boolean { if (k === 0) { return t.isSame(b); } for (let i = 0; i < b.n*2; i++) { v.push(i); const s = t.clone(); if (i < b.n) { s.operateCol(i); } else { s.operateRow(i-b.n); } if (search(b,k-1,s,v)) { return true; } v.pop(); } } function cycle(p: number[]): number { let t = p.slice(); let w = p.slice(); for (let cnt = 1; ; cnt++) { for (let i = 0; i < p.length; i++) { t[p[i]] = w[i]; } let ok = true; for (let i = 0; i < p.length; i++) { if (p[i] !== t[i]) { ok = false; break; } } if (ok) { return cnt; } let tmp = t; t = w; w = tmp; } } class PPuzzle { n: number; matrix: number[][]; iCol: number[]; iRow: number[]; constructor(n: number) { this.n = n; this.matrix = []; this.iCol = []; this.iRow = []; } scan(input: number[]): PPuzzle { const n =this.n; this.matrix = new Array(n).fill(null); for (let r = 0; r < n; r++) { this.matrix[r] = new Array(n).fill(0); for (let c = 0; c < n; c++) { this.matrix[r][c] = input.shift() - 1; } } this.iCol = new Array(n).fill(0).map((_,i) => i); this.iRow = new Array(n).fill(0).map((_,i) => i); return this; } clone(): PPuzzle { const copied = new PPuzzle(this.n); copied.matrix = this.matrix; copied.iCol = this.iCol.slice(); copied.iRow = this.iRow.slice(); return copied; } at(r: number, c: number): number { return this.matrix[this.iRow[r]][this.iCol[c]]; } selectCol(x: number): number[] { return new Array(this.n).fill(0).map((_,r) => this.at(r, x)); } selectRow(y: number): number[] { return new Array(this.n).fill(0).map((_,c) => this.at(y, c)); } operateCol(x: number): void { const p = this.selectCol(x); const t = this.iCol.slice(); p.forEach((v, i) => this.iCol[v] = t[i]); } operateRow(y: number): void { const p = this.selectRow(y); const t = this.iRow.slice(); p.forEach((v, i) => this.iRow[v] = t[i]); } isSame(other: PPuzzle): boolean { for (let r = 0; r < this.n; r++) { for (let c = 0; c < this.n; c++) { if (this.at(r,c) !== other.at(r,c)) { return false; } } } return true; } }