結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2024-12-20 01:53:56
言語 PHP
(843.2)
結果
AC  
実行時間 376 ms / 2,000 ms
コード長 2,947 bytes
コンパイル時間 1,965 ms
コンパイル使用メモリ 32,308 KB
実行使用メモリ 32,656 KB
最終ジャッジ日時 2024-12-20 01:54:07
合計ジャッジ時間 7,700 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
No syntax errors detected in Main.php

ソースコード

diff # 

<?php

class PPuzzle
{
	private $n;
	private $icol;
	private $irow;
	private $matrix;
	
	public static function read($n)
	{
		$pp = new PPuzzle();
		$pp->n = $n;
		$pp->icol = array_combine(range(1, $n), range(1, $n));
		$pp->irow = array_combine(range(1, $n), range(1, $n));
		$pp->matrix = array_fill(1, $n, []);
		for ($r = 1; $r <= $n; $r++) {
			$s = explode(" ", fgets(STDIN));
			$pp->matrix[$r] = array_fill(1, $n, 0);
			for ($c = 1; $c <= $n; $c++) {
				$pp->matrix[$r][$c] = intval(array_shift($s));
			}
		}
		return $pp;
	}
	
	public function size() {
		return $this->n;
	}
	
	public function at($r, $c) {
		return $this->matrix[$this->irow[$r]][$this->icol[$c]];
	}
	
	public function selectCol($x) {
		$v = array_fill(1, $this->n, 0);
		for ($r = 1; $r <= $this->n; $r++) {
			$v[$r] = $this->at($r, $x);
		}
		return $v;
	}
	
	public function selectRow($y) {
		$v = array_fill(1, $this->n, 0);
		for ($c = 1; $c <= $this->n; $c++) {
			$v[$c] = $this->at($y, $c);
		}
		return $v;
	}
	
	public function operateCol($x) {
		$p = $this->selectCol($x);
		$t = array_fill(1, $this->n, 0);
		for ($i = 1; $i <= $this->n; $i++) {
			$t[$p[$i]] = $this->icol[$i];
		}
		$this->icol = $t;
	}

	public function operateRow($y) {
		$p = $this->selectRow($y);
		$t = array_fill(1, $this->n, 0);
		for ($i = 1; $i <= $this->n; $i++) {
			$t[$p[$i]] = $this->irow[$i];
		}
		$this->irow = $t;
	}
	
	public function isSame($other) {
		for ($r = 1; $r <= $this->n; $r++) {
			for ($c = 1; $c <= $this->n; $c++) {
				if ($this->at($r,$c) !== $other->at($r,$c)) {
					return false;
				}
			}
		}
		return true;
	}
}

function search($b, $k, $t, &$v) {
	if ($k === 0) {
		return $t->isSame($b);
	}
	for ($i = 1; $i <= $b->size()*2; $i++) {
		$v[] = $i;
		$s = clone $t;
		if ($i <= $b->size()) {
			$s->operateCol($i);
		} else {
			$s->operateRow($i-$b->size());
		}
		if (search($b,$k-1,$s,$v)) {
			return true;
		}
		array_pop($v);
	}
	return false;
}

function cycle($p) {
	$t = array_fill(1, count($p), 0);
	$w = array_slice($p, 0, null, true);
	for ($cnt = 1;; $cnt++) {
		for ($i = 1; $i <= count($p); $i++) {
			$t[$p[$i]] = $w[$i];
		}
		if ($p == $t) {
			return $cnt;
		}
		list($t, $w) = [$w, $t];
	}
}

function solve($n, $k, $a, $b) {
	$ops = [];
	search($b, $k, $a, $ops);
	$ans = [];
	$t = clone $a;
	foreach ($ops as $op) {
		if ($op <= $n) {
			$p = $t->selectCol($op);
			$t->operateCol($op);
		} else {
			$p = $t->selectRow($op-$n);
			$t->operateRow($op-$n);
		}
		$z = $op <= $n ? $op : ($op-$n);
		$tmp = [];
		for ($cnt = cycle($p)-1; $cnt > 0; $cnt--) {
			$z = $p[$z];
			$tmp[] = $op <= $n ? $z : ($z+$n);
		}
		$ans = array_merge($tmp, $ans);
	}
	return $ans;	
}


fscanf(STDIN, "%d%d", $n, $k);
$a = PPuzzle::read($n);
$b = PPuzzle::read($n);
$ans = solve($n, $k, $a, $b);
echo count($ans), PHP_EOL;
foreach ($ans as $op) {
	if ($op <= $n) {
		echo "C ", $op, PHP_EOL;
	} else {
		echo "R ", ($op-$n), PHP_EOL;
	}
}
0