paiza learning 升级练习 广度优先搜索/深度优先搜索菜单 JavaScript 区域数

区域数（相当于paiza rank A）

我试图用 JavaScript 解决它。

答案代码示例 1 堆栈中的深度优先搜索

将网格的一个正方形作为搜索的起点。

准备一个堆栈并执行深度优先搜索。

搜索到的地点将被标记为已搜索。

以相同的方式搜索网格中的所有方格。

JavaScript

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");
//グリッドの行数 H , 列数 W
const [H, W] = lines[0].split(" ").map(Number);
//グリッド
const grid = lines.slice(1, H + 1).map(row => row.split(""));

let count = 0; //区画の数
//探索のスタート地点を決める
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        if (grid[i][j] !== ".") {
            continue;//探索できないなら次
        } else {
            count += 1;//探索できるならカウント
        }
        //スタックでの深さ優先探索     
        let stack = [[i, j]];//スタート地点のy, x座標
        //探索
        while (stack.length > 0) {
            const [y, x] = stack.pop();
            //探索できるところを訪問済にする
            //上
            if (y - 1 >= 0 && grid[y - 1][x] === ".") {
                grid[y - 1][x] = "#";//訪問済に
                stack.push([y - 1, x]);
            }
            //右
            if (x + 1 < W && grid[y][x + 1] === "."){
                grid[y][x + 1] = "#";
                stack.push([y, x + 1]);
            }
            //下
            if (y + 1 < H && grid[y + 1][x] === ".") {
                grid[y + 1][x] = "#";
                stack.push([y + 1, x]);
            }
            //左
            if (x - 1 >= 0 && grid[y][x - 1] === ".") {
                grid[y][x - 1] = "#";
                stack.push([y, x - 1]);
            }
        }
    }
}
console.log(count);

答案代码示例 2 使用函数 1 进行深度优先搜索（请参阅 C++ 或 Java 的模型答案）

定义深度优先搜索函数。

从网格的一个正方形开始执行深度优先搜索功能。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf8").trim();
const lines = input.split("\n");

const [H, W] = lines[0].split(" ").map(Number);

let grid = lines.slice(1).map(line => line.split(""));
//深さ優先探索関数定義
const dfs = (sy, sx) => {

        //移動は上,右,下,左の順
        if (sy - 1 >= 0 && grid[sy - 1][sx] === ".") {
            grid[sy - 1][sx] = "*";//訪問済み
            dfs(sy - 1, sx);
        }
         if (sx + 1 < W && grid[sy][sx + 1] === ".") {
            grid[sy][sx + 1] = "*";
            dfs(sy, sx + 1);
        }
        if (sy + 1 < H && grid[sy + 1][sx] === ".") {
            grid[sy + 1][sx] = "*";
            dfs(sy + 1, sx);
        }
        if (sx - 1 >= 0 && grid[sy][sx - 1] === ".") {
            grid[sy][sx - 1] = "*";
            dfs(sy, sx - 1);
        }
    
};

let ans = 0;//いくつの区画
//スタート地点を決める
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        if (grid[i][j] === ".") {
            ans += 1;
            grid[i][j] = "*";
            dfs(i, j);//探索実行
        }
    }
}
console.log(ans);

答案代码示例3 函数深度优先搜索2（参考Python3的模型答案）

定义深度优先搜索函数。上下、左右结合。

从网格的一个正方形开始执行深度优先搜索。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf8").trim();
const lines = input.split("\n");

const [H, W] = lines[0].split(" ").map(Number);

let grid = lines.slice(1).map(line => line.split(""));
//深さ優先探索関数定義
const dfs = (sy, sx) => {
    grid[sy][sx] = "#";//訪問済みに  
    for (let i = -1; i <= 1; i += 2) {
        //上下
        if (0 <= sy + i && sy + i < H && grid[sy + i][sx] === ".") {
            dfs(sy + i, sx);
        }
        //左右
        if (0 <= sx + i && sx + i < W && grid[sy][sx + i] === ".") {
            dfs(sy, sx + i);
        }
    }
};

let ans = 0;//いくつの区画
//スタート地点決める
for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        if (grid[i][j] === ".") {
            dfs(i, j);//探索実行
            ans++;
        }
    }
}
console.log(ans);

原创声明：本文系作者授权爱码网发表，未经许可，不得转载;

原文地址：https://www.likecs.com/show-308626194.html