結果

問題 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;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0