幅優先探索

初期状態

ある状態から遷移できる状態の配列を返す関数

ある状態が条件を満たしているかを判定する関数

終了状態

を渡した時に幅優先探索を実行する

code: BFS.js

class Bfs {

constructor() {

this.memo = [];

this.toKey = (e) => JSON.stringify(e);

}

initialElem(e) {

if (e == null) { return this.initialElem; }

this.initialElem = e;

return this;

}

finalElem(e) {

if (e == null) { return this.finalElem; }

this.finalElem = e;

this.finalElemKey = this.toKey(e);

return this;

}

check(func) {

if (func == null) { return this.checkFunc; }

this.checkFunc = func;

return this;

}

next(func) {

if (func == null) { return this.nextFunc; }

this.nextFunc = func;

return this;

}

search() {

const queue = new Queue();

while(queue.exist) {

const p = queue.shift();

for (const next of nexts) {

if (!this.checkFunc(next)) continue;

if (this.getMemo(next) !== undefined) continue;

}

}

if (this.finalElem) { return this.getMemo(this.finalElem); }

return this;

}

isFinal(e) { return this.toKey(e) === this.finalElemKey; }

}

サンプル

ABC 007 C

code: abc007_c.js

class Main {

solve() {

const size = input.nextIntArr();

const s = input.nextIntArr();

const g = input.nextIntArr();

console.log(new Bfs()

.initialElem(s)

.finalElem(g)

.search()

);

}

}

Issue

深さ優先探索