幅優先探索・深さ優先探索メニュー【グリッドの深さ優先探索 (3 マス)・領域の個数】
【グリッドの深さ優先探索 (3 マス)】コード 1/2(再起関数)
reader.on('close', () => {
const dfs = (h, w, y, x, times) => {
if (times === 3) { // 3 マス移動したら…
console.log(y, x); // 座標を出力
return;
}
// 上,右,下,左の順に探索
if (0 <= y - 1) { // エリア内の…
dfs(h, w, y - 1, x, times + 1); // 上へ移動
}
if (x + 1 < w) { // エリア内の…
dfs(h, w, y, x + 1, times + 1); // 右へ移動
}
if (y + 1 < h) { // エリア内の…
dfs(h, w, y + 1, x, times + 1); // 下へ移動
}
if (0 <= x - 1) { // エリア内の…
dfs(h, w, y, x - 1, times + 1); // 左へ移動
}
};
const [H, W, Y, X] = lines[0].split(' ').map(Number);
dfs(H, W, Y, X, 0);
});
問題の意図がイマイチ理解できなかった (´·ω·`)。
回答コード例を参照しました。
【グリッドの深さ優先探索 (3 マス)】コード 2/2(スタック)
reader.on('close', () => {
const dfs = (stack) => {
while (stack.length) {
const [times, y, x] = stack.pop(); // スタックから値を取出([移動回数, Y座標, X座標])
if (times === 3) { // 3 コマ移動したら…
console.log(y, x); // 座標を出力して…
continue; // 残りの処理をスキップ
}
// 上,右,下,左の順に探索
const move = [-1, 1];
for (const m of move) {
if (0 <= x + m && x + m < W) {
stack.push([times + 1, y, x + m]); // スタックに値を保存(上下へ移動)
}
if (0 <= y - m && y - m < H) {
stack.push([times + 1, y - m, x]); // スタックに値を保存(右左へ移動)
}
}
}
};
const [H, W, Y, X] = lines[0].split(' ').map(Number);
dfs([[0, Y, X]]);
});回答コード例を参照しました。
【領域の個数】コード
reader.on('close', () => {
const dfs = (y, x) => {
M[y][x] = '#'; // M[y][x] を '#' に変換
const move = [-1, 1];
for (const m of move) {
if (0 <= y + m && y + m < H && M[y + m][x] === '.') { // M[y + m][x] がエリア内なら…
dfs(y + m, x); // 再起処理
}
if (0 <= x + m && x + m < W && M[y][x + m] === '.') { // M[y][x + m] がエリア内なら…
dfs(y, x + m); // 再起処理
}
}
};
const [H, W] = lines.shift().split(' ').map(Number);
let areas = 0;
const M = [];
for (let i = 0; i < H; i++) {
M.push(lines.shift().split(''));
}
for (let i = 0; i < H; i++) {
for (let j = 0; j < W; j++) { // M の要素を一つ一つ調べて…
if (M[i][j] === '.') { // '.'なら…
dfs(i, j); // dfs(i, j) を呼び出し
areas++;
}
}
}
console.log(areas);
});領域内の’.’を見つけて’#’に置き換え。全て’#’になるまで繰り返し。
コメント