結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2024-12-19 19:10:59
言語 JavaScript
(node v23.5.0)
結果
AC  
実行時間 511 ms / 2,000 ms
コード長 2,930 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 6,692 KB
実行使用メモリ 50,956 KB
最終ジャッジ日時 2024-12-19 19:11:15
合計ジャッジ時間 11,712 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

{
	let data = '';
	process.stdin.on('data', (chunk) => { data += chunk; });
	process.stdin.on('end', () => { run(data); });
	process.stdin.setEncoding('utf8');
	process.stdin.resume();
}

function run(data) {
	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, k, a, b) {
	const ops = [];
	search(b, k, a, ops);
	
	let ans = [];
	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, k, t, v) {
	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) {
	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 {
	
	constructor(n) {
		this.n = n;
		this.matrix = [];
		this.iCol = [];
		this.iRow = [];
	}
	scan(input) {
		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() {
		const copied = new PPuzzle(this.n);
		copied.matrix = this.matrix;
		copied.iCol = this.iCol.slice();
		copied.iRow = this.iRow.slice();
		return copied;
	}
	
	at(r, c) {
		return this.matrix[this.iRow[r]][this.iCol[c]];
	}
	
	selectCol(x) {
		return new Array(this.n).fill(0).map((_,r) => this.at(r, x));
	}
	
	selectRow(y) {
		return new Array(this.n).fill(0).map((_,c) => this.at(y, c));
	}
	
	operateCol(x) {
		const p = this.selectCol(x);
		const t = this.iCol.slice();
		p.forEach((v, i) => this.iCol[v] = t[i]);
	}
	
	operateRow(y) {
		const p = this.selectRow(y);
		const t = this.iRow.slice();
		p.forEach((v, i) => this.iRow[v] = t[i]);
	}
	
	isSame(other) {
		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;
	}
}
0