結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2024-12-23 09:31:25
言語 TypeScript
(5.7.2)
結果
AC  
実行時間 410 ms / 2,000 ms
コード長 3,250 bytes
コンパイル時間 8,235 ms
コンパイル使用メモリ 228,728 KB
実行使用メモリ 49,568 KB
最終ジャッジ日時 2024-12-31 17:03:52
合計ジャッジ時間 17,460 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/// <reference types="/home/linuxbrew/.linuxbrew/lib/node_modules/@types/node" />
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;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0