华为OD机试真题 JavaScript 实现【查找单入口空闲区域】【2022 Q4 100分】，附详细解题思路

华为OD机试真题 JavaScript 实现【查找单入口空闲区域】【2022 Q4 100分】，附详细解题思路-LMLPHP

一、题目描述

给定一个 m x n 的矩阵，由若干字符 ‘X’ 和 ‘O’构成，’X’表示该处已被占据，’O’表示该处空闲，请找到最大的单入口空闲区域。

解释：

空闲区域是由连通的’O’组成的区域，位于边界的’O’可以构成入口，

单入口空闲区域即有且只有一个位于边界的’O’作为入口的由连通的’O’组成的区域。

如果两个元素在水平或垂直方向相邻，则称它们是“连通”的。

二、输入描述

第一行输入为两个数字，第一个数字为行数m，第二个数字为列数n，两个数字以空格分隔，1<=m,n<=200。

剩余各行为矩阵各行元素，元素为‘X’或‘O’，各元素间以空格分隔。

三、输出描述

若有唯一符合要求的最大单入口空闲区域，输出三个数字

第一个数字为入口行坐标（0~m-1）
第二个数字为入口列坐标（0~n-1）
第三个数字为区域大小
三个数字以空格分隔；

若有多个符合要求，则输出区域大小最大的，若多个符合要求的单入口区域的区域大小相同，则此时只需要输出区域大小，不需要输出入口坐标。

若没有，输出NULL。

四、解题思路

这道题我们需要找到最大的单入口空闲区域。因此，我们需要遍历矩阵，找到所有位于边界的 0，然后计算以这些 0 为入口的最大空闲区域的大小。最后，找到最大的空闲区域即可。

对于每个入口，我们可以使用 DFS 算法遍历矩阵，计算以当前入口为起点的空闲区域的大小。在遍历过程中，我们需要标记已经访问过的位置，避免重复计算。同时，如果当前位置不是边界位置，我们需要确保它不是入口，否则，我们会重复计算已经计算过的区域。

五、JavaScript算法源码

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let rows, cols;
let board = [];
let directions = [[0, -1], [0, 1], [-1, 0], [1, 0]];
let visited = new Set();

function dfs(row, col, count, enter) {
    let pos = row.toString() + "-" + col.toString();

    if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] === "X" || visited.has(pos)) {
        return count;
    }

    visited.add(pos);

    if (row === 0 || row === rows - 1 || col === 0 || col === cols - 1) {
        enter.push([row, col]);
    }

    count++;

    for (let dir of directions) {
        let newRow = row + dir[0];
        let newCol = col + dir[1];
        count = dfs(newRow, newCol, count, enter);
    }

    return count;
}

rl.on('line', function (line) {
    if (!rows) {
        [rows, cols] = line.split(' ').map(Number);
    } else {
        board.push(line.split(' '));
        if (board.length === rows) {
            let ans = [];

            for (let i = 0; i < rows; i++) {
                for (let j = 0; j < cols; j++) {
                    if (board[i][j] === "O" && !visited.has(i.toString() + "-" + j.toString())) {
                        let enter = [];
                        let count = dfs(i, j, 0, enter);
                        if (enter.length === 1) {
                            let pos = enter[0];
                            ans.push([pos[0], pos[1], count]);
                        }
                    }
                }
            }

            if (ans.length === 0) {
                console.log("NULL");
            } else {
                ans.sort((a, b) => b[2] - a[2]);
                if (ans.length === 1 || ans[0][2] > ans[1][2]) {
                    console.log(ans[0].join(' '));
                } else {
                    console.log(ans[0][2]);
                }
            }

            rows = cols = null;
            board = [];
            visited.clear();
        }
    }
});

六、效果展示

1、输入

5 4
X X X X
X O O O
X X X X
X O O O
X X X X

2、输出

3、说明

存在两个大小为3的最大单入口区域，两个入口坐标分别为(1,3)、(3,3)。

华为OD机试真题 JavaScript 实现【查找单入口空闲区域】【2022 Q4 100分】，附详细解题思路-LMLPHP

🏆下一篇：华为OD机试真题 JavaScript 实现【相对开音节】【2022Q4 100分】，附详细解题思路

🏆本文收录于，华为OD机试（JavaScript）真题（A卷+B卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，可加入华为OD刷题群（私信即可），发现新题目，随时更新，全天CSDN在线答疑。

哪吒