简单网站html模板下载地址,免费的网页设计成品详解,做网站的教程,建设工程交易中心官网给定一个mxn的矩阵#xff0c;由若干字符X和O构成#xff0c;X表示该处已被占据#xff0c;O表示该处空闲#xff0c;请找到最大的单入口空闲区域
解释:
空闲区域是由连通的O组成的区域#xff0c;位于边界的O可以构成入口.单入口空闲区域即有且只有一个位于边界的O作为…给定一个mxn的矩阵由若干字符X和O构成X表示该处已被占据O表示该处空闲请找到最大的单入口空闲区域
解释:
空闲区域是由连通的O组成的区域位于边界的O可以构成入口.单入口空闲区域即有且只有一个位于边界的O作为入口的由连通的O组成的区域.如果两个元素在水平或垂直方向相邻则称它们是“连通”的
输入描述
第一行输入为两个数字第一个数字为行数 m第二个数字为列数 n两个数字以空格分隔
1m,n200.
剩余各行为矩阵各行元素元素为X或O各元素间以空格分隔
输出描述
若有唯一符合要求的最大单入口空闲区域输出三个数字
第一个数字为入口行坐标(0~m-1) 第二个数字为入口列坐标(0~n-1) 第三个数字为区域大小 三个数字以空格分隔;
若有多个符合要求则输出区域大小最大的若多个符合要求的单入口区域的区域大小相同 则此时只需要输出区域大小不需要输出入口坐标
若没有输出 NULL
用例
输出输出4 4 X X X X X O O X X O O X X O X X3 1 5 思考一DFS 矩阵搜索问题可以通过 DFS 或 BFS 解决。先看 DFS要求统计单入口区域大小那么可以围绕着矩阵边界寻找元素为‘O的位置作为起点进行深度优先搜索。每个入口表示一次 DFS过程中我们要统计区域大小即元素 ’O 的数量怎么把这个数量和当前 DFS 进行关联呢由于一般 DFS 是递归实现这里也是采用递归实现 DFS 过程因此我们每递归调用一次 dfs 函数就会开启一个临时栈这个栈在结束时会销毁内部关联的数据可以通过引用参数把函数栈的计算数据保存起来。也就是说可以在DFS起点的时候就传递一个对象或数组存放当前 DFS 起点坐标及入口坐标、区域大小 count 初始化参数值为 0然后搜索过程中不断更新这个对象的属性值。当我们搜索到另一个位于边界上的元素O时表明当前 DFS 搜索已经包含了两个入口显然不满足单入口要求需要丢弃当前搜索结果终止本次 DFS但并不能立即终止递归。递归搜索是分叉的树状结构在某个分支节点上遇到了该结束的状态但是其它分支依然在进行展开我们没法立即通知它们完结销毁整棵递归树 。 这时候需要把那个引用传递给 dfs 函数的对象参数更新下比如把 count 置为 -1在递归函数中判断如果 count 是 -1 就回溯因为引用传递的参数对象是共享的因此所有递归调用的函数栈中都能看到相同的状态都立即回溯最终整棵递归树就销毁了。如果搜索整个过程顺利没有遇到第二个入口那么最终这次 DFS 的统计的区域大小 count 和 起点坐标 x,y 都要与全局的结果进行比较更新保存最大的count已存在相同大小的 count 就更新全局变量 isMult 为 true 表示存在多个相同大小的单入口区域。但实际实现感觉这种通过函数的引用参数保存搜索结果有时候处理逻辑写起来并不是很容易且直观。所以还有一种通过全局的字典变量来记录每次 DFS 搜索结果更简单些就像记录元素是否被访问过的备忘录变量 visited数组。用入口的位置坐标以空格作为分割拼接字符串作为字典的 keyJavaScript 就用 Map 来处理用区域大小 count 作为字典的值。这样 dfs函数只要传递当前元素位置坐标 和 起始位置[x,y] 就行了根据key 来更新对应的数据。最后统计字典中最大的数值有重复的最大的就只输出最大数值没有重复最大值也把入口坐标输出字典为空表示没找到单入口区域输出 NULL。 算法过程
输入处理读取网格尺寸 m 和 n然后读取整个网格内容初始化数据结构创建与网格大小相同的 visited 数组并初始化为 false创建入口映射 entryMap边界遍历 遍历左右边界列 0 和列 n-1对未访问的 O 点启动 DFS遍历上下边界行 0 和行 m-1对未访问的 O 点启动 DFS DFS 搜索 标记当前点为已访问若当前点是边界点且非起点删除当前入口并返回递归搜索上下左右四个方向的相邻点 结果处理 遍历所有合法入口区域找出最大区域若存在多个最大区域仅输出大小否则输出坐标和大小 时间复杂度O (mn) 空间复杂度O (mn) 参考代码
function solution() {const [m, n] readline().split( ).map(Number);const mtx [];for (let i 0; i m; i) {mtx.push(readline().split( ));}const visited Array.from({ length: m }, () new Array(n).fill(false));const entryMap new Map();const dfs function (i, j, [x, y]) {// 已访问过或者当前元素不可通行直接返回if (visited[i][j] || mtx[i][j] X) return;visited[i][j] true;const key ${x} ${y};if (!entryMap.has(key)) return; // key 被干掉了好吧...entryMap.set(key, entryMap.get(key) 1); // 统计区域大小if ((i ! x || j ! y) (i 0 || i m-1 || j 0 || j n-1)) {// 找到了另一个入口删除当前起点区域作废entryMap.delete(key);return;}if (i - 1 0) {// 判断左侧非边界区域是否可搜索dfs(i - 1, j, [x, y]);}if (i 1 m) {// 判断右侧非边界区域是否可搜索dfs(i 1, j, [x, y]);}if (j - 1 0) {// 判断上方非边界区域是否可搜索dfs(i, j - 1, [x, y]);}if (j 1 n) {// 判断下方非边界区域是否可搜索dfs(i, j 1, [x, y]);}};// 固定列寻找左右边界上的入口开始搜索let key;for (let i 0; i m; i) {if (!visited[i][0] mtx[i][0] O) {key ${i} 0;entryMap.set(key, 0);dfs(i, 0, [i, 0]);}if (!visited[i][n-1] mtx[i][n-1] O) {key ${i} ${n-1};entryMap.set(key, 0);dfs(i, n-1, [i, n-1]);}}// 固定行 寻找上下边界上的入口开始搜索for (let i 0; i n; i) {if (!visited[0][i] mtx[0][i] O) {key 0 ${i};entryMap.set(key, 0);dfs(0, i, [0, i]);}if (!visited[m - 1][i] mtx[m - 1][i] O) {key ${m-1} ${i};entryMap.set(key, 0);dfs(m-1, i, [m-1, i]);}}// console.log(entryMap);if (entryMap.size 0) {console.log(NULL);return;}let maxSize 0;let coordinate undefined;let isMult false;for (let [k, v] of entryMap) {if (coordinate) {if (v maxSize) {maxSize v;coordinate k;isMult false;} else if (v maxSize) {isMult true;}} else {maxSize v;coordinate k;}}if (isMult) {console.log(maxSize);} else {console.log(coordinate maxSize);}
}const cases [4 4
X X X X
X O O X
X O O X
X O X X,4 5X X X X XO O O O XX O O O XX O X X O,5 4X X X XX 0 0 0X 0 0 0X 0 0 XX X X X,5 4X X X XX O O OX X X XX O O OX X X X
];let caseIndex 0;
let lineIndex 0;const readline (function () {let lines [];return function () {if (lineIndex 0) {lines cases[caseIndex].trim().split(\n).map((line) line.trim());}return lines[lineIndex];};
})();cases.forEach((_, i) {caseIndex i;lineIndex 0;solution();
});思考二BFS
有了上面的 DFS 解法基础BFS 实现就很简单了只用修改下搜索的方式队列存储要遍历的元素迭代访问队列中的每个元素进行统计直至队列为空bfs 函数直接返回单入口区域大小对于非单入口区域返回 0 。 算法过程
输入处理读取网格尺寸 m 和 n然后读取整个网格内容初始化数据结构创建与网格大小相同的 visited 数组并初始化为 false创建入口映射 entryMap边界遍历 遍历左右边界列 0 和列 n-1对未访问的 O 点启动 BFS遍历上下边界行 0 和行 m-1对未访问的 O 点启动 BFS BFS 搜索 初始化队列并将起点加入队列当队列不为空时 取出队首元素若已访问或为 X 则跳过标记当前点为已访问若当前点是边界点且非起点清空计数器并终止 BFS计数器加 1将上下左右四个方向的合法相邻点加入队列 返回区域大小若发现多入口则为 0 结果处理 遍历所有合法入口区域找出最大区域若存在多个最大区域仅输出大小否则输出坐标和大小 时间复杂度O (mn) 空间复杂度O (mn) 参考代码
function solution() {const [m, n] readline().split( ).map(Number);const mtx [];for (let i 0; i m; i) {mtx.push(readline().split( ));}const visited Array.from({ length: m }, () new Array(n).fill(false));const entryMap new Map();const bfs function (queue, [x, y]) {let count 0;while (queue.length) {let [i, j] queue.shift();if (visited[i][j] || mtx[i][j] X) continue;visited[i][j] true;if ((i ! x || j ! y) (i 0 || i m-1 || j 0 || j n-1)) {// 找到了另一个入口停止迭代区域作废count 0;break;}count;if (i-1 0) {queue.push([i-1, j]);}if (i1 m) {queue.push([i1, j]);}if (j-1 0) {queue.push([i, j-1]);}if (j1 n) {queue.push([i, j1]);}}return count;};// 固定列寻找左右边界上的入口开始搜索for (let i 0; i m; i) {if (!visited[i][0] mtx[i][0] O) {entryMap.set(${i} 0, bfs([[i, 0]], [i, 0]));}if (!visited[i][n-1] mtx[i][n-1] O) {entryMap.set(${i} ${n-1}, bfs([[i, n-1]], [i, n-1]));}}// 固定行 寻找上下边界上的入口开始搜索for (let i 0; i n; i) {if (!visited[0][i] mtx[0][i] O) {entryMap.set(0 ${i}, bfs([[0, i]], [0, i]));}if (!visited[m - 1][i] mtx[m - 1][i] O) {entryMap.set(${m-1} ${i}, bfs([[m-1, i]], [m-1, i]));}}// console.log(entryMap);if (entryMap.size 0) {console.log(NULL);return;}let maxSize 0;let coordinate undefined;let isMult false;for (let [k, v] of entryMap) {if (coordinate) {if (v maxSize) {maxSize v;coordinate k;isMult false;} else if (v maxSize) {isMult true;}} else {maxSize v;coordinate k;}}if (isMult) {console.log(maxSize);} else {console.log(coordinate maxSize);}
}const cases [4 4
X X X X
X O O X
X O O X
X O X X,4 5X X X X XO O O O XX O O O XX O X X O,5 4X X X XX 0 0 0X 0 0 0X 0 0 XX X X X,5 4X X X XX O O OX X X XX O O OX X X X
];let caseIndex 0;
let lineIndex 0;const readline (function () {let lines [];return function () {if (lineIndex 0) {lines cases[caseIndex].trim().split(\n).map((line) line.trim());}return lines[lineIndex];};
})();cases.forEach((_, i) {caseIndex i;lineIndex 0;solution();
});
