珠海建设工程网站抚顺市+网站建设

珠海建设工程网站,抚顺市+网站建设,做网站框架浏览时怎么变长,工商法律网站建设孤岛的总面积 题目描述 给定一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的矩阵#xff0c;岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域#xff0c;且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛…孤岛的总面积题目描述给定一个由 1陆地和 0水组成的矩阵岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。现在你需要计算所有孤岛的总面积岛屿面积的计算方式为组成岛屿的陆地的总数。输入描述第一行包含两个整数 N, M表示矩阵的行数和列数。之后 N 行每行包含 M 个数字数字为 1 或者 0。输出描述输出一个整数表示所有孤岛的总面积如果不存在孤岛则输出 0。输入示例4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1输出示例1提示信息在矩阵中心部分的岛屿因为没有任何一个单元格接触到矩阵边缘所以该岛屿属于孤岛总面积为 1。数据范围1 M, N 50。思路本题要我们找到不靠边的陆地的面积那么就只需要先从周边找到陆地通过深搜或者广搜将周边靠陆地并且相邻的陆地全部变成海洋最后重新遍历剩下的陆地面积就是我们要求的孤岛面积。如图绿色都是接触边缘的岛屿在遇到地图周边陆地的时候将1都变为0此时地图为这样代码示例dfsconst r1 require(readline).createInterface({ input: process.stdin }); // 创建readline接口 let iter r1[Symbol.asyncIterator](); // 创建异步迭代器 const readline async () (await iter.next()).value; let graph // 地图 let N, M // 地图大小 let count 0 // 孤岛的总面积 const dir [[0, 1], [1, 0], [0, -1], [-1, 0]] //方向 // 读取输入初始化地图 const initGraph async () { let line await readline(); [N, M] line.split( ).map(Number); graph new Array(N).fill(0).map(() new Array(M).fill(0)) for (let i 0; i N; i) { line await readline() line line.split( ).map(Number) for (let j 0; j M; j) { graph[i][j] line[j] } } } /** * description: 从xy开始深度优先遍历地图 * param {*} graph 地图 * param {*} x 开始搜索节点的下标 * param {*} y 开始搜索节点的下标 * return {*} */ const dfs (graph, x, y) { if(graph[x][y] 0) return graph[x][y] 0 // 标记为海洋 for (let i 0; i 4; i) { let nextx x dir[i][0] let nexty y dir[i][1] if (nextx 0 || nextx N || nexty 0 || nexty M) continue dfs(graph, nextx, nexty) } } (async function () { // 读取输入初始化地图 await initGraph() // 遍历地图左右两边 for (let i 0; i N; i) { if (graph[i][0] 1) dfs(graph, i, 0) if (graph[i][M - 1] 1) dfs(graph, i, M - 1) } // 遍历地图上下两边 for (let j 0; j M; j) { if (graph[0][j] 1) dfs(graph, 0, j) if (graph[N - 1][j] 1) dfs(graph, N - 1, j) } count 0 // 统计孤岛的总面积 for (let i 0; i N; i) { for (let j 0; j M; j) { if (graph[i][j] 1) count } } console.log(count); })()bfsconst r1 require(readline).createInterface({ input: process.stdin }); // 创建readline接口 let iter r1[Symbol.asyncIterator](); // 创建异步迭代器 const readline async () (await iter.next()).value; let graph // 地图 let N, M // 地图大小 let count 0 // 孤岛的总面积 const dir [[0, 1], [1, 0], [0, -1], [-1, 0]] //方向 // 读取输入初始化地图 const initGraph async () { let line await readline(); [N, M] line.split( ).map(Number); graph new Array(N).fill(0).map(() new Array(M).fill(0)) for (let i 0; i N; i) { line await readline() line line.split( ).map(Number) for (let j 0; j M; j) { graph[i][j] line[j] } } } /** * description: 从xy开始广度优先遍历地图 * param {*} graph 地图 * param {*} x 开始搜索节点的下标 * param {*} y 开始搜索节点的下标 * return {*} */ const bfs (graph, x, y) { let queue [] queue.push([x, y]) graph[x][y] 0 // 只要加入队列立刻标记 while (queue.length) { let [xx, yy] queue.shift() for (let i 0; i 4; i) { let nextx xx dir[i][0] let nexty yy dir[i][1] if (nextx 0 || nextx N || nexty 0 || nexty M) continue if (graph[nextx][nexty] 1) { queue.push([nextx, nexty]) graph[nextx][nexty] 0 // 只要加入队列立刻标记 } } } } (async function () { // 读取输入初始化地图 await initGraph() // 遍历地图左右两边 for (let i 0; i N; i) { if (graph[i][0] 1) bfs(graph, i, 0) if (graph[i][M - 1] 1) bfs(graph, i, M - 1) } // 遍历地图上下两边 for (let j 0; j M; j) { if (graph[0][j] 1) bfs(graph, 0, j) if (graph[N - 1][j] 1) bfs(graph, N - 1, j) } count 0 // 统计孤岛的总面积 for (let i 0; i N; i) { for (let j 0; j M; j) { if (graph[i][j] 1) count } } console.log(count); })()沉没孤岛题目描述给定一个由 1陆地和 0水组成的矩阵岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。现在你需要将所有孤岛“沉没”即将孤岛中的所有陆地单元格1转变为水域单元格0。输入描述第一行包含两个整数 N, M表示矩阵的行数和列数。之后 N 行每行包含 M 个数字数字为 1 或者 0表示岛屿的单元格。输出描述输出将孤岛“沉没”之后的岛屿矩阵。输入示例4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1输出示例1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1提示信息将孤岛沉没数据范围1 M, N 50思路本题和上一题完全反过来了上一题是记录地图中间的空格数本题是要把地图中间的所有1改成0不过两者在思路上大差不差。我们还是从地图周边出发将周边空格相邻的陆地全部标记然后再遍历一遍地图遇到没有打标记的陆地那就是孤岛全部改成水域即可。这总共需要三步先dfs或者bfs将所有的1改成2将中间的1改成0再把之前所有的2改回1如图代码示例dfsconst r1 require(readline).createInterface({ input: process.stdin }); // 创建readline接口 let iter r1[Symbol.asyncIterator](); // 创建异步迭代器 const readline async () (await iter.next()).value; let graph // 地图 let N, M // 地图大小 const dir [[0, 1], [1, 0], [0, -1], [-1, 0]] //方向 // 读取输入初始化地图 const initGraph async () { let line await readline(); [N, M] line.split( ).map(Number); graph new Array(N).fill(0).map(() new Array(M).fill(0)) for (let i 0; i N; i) { line await readline() line line.split( ).map(Number) for (let j 0; j M; j) { graph[i][j] line[j] } } } /** * description: 从xy开始深度优先遍历地图 * param {*} graph 地图 * param {*} x 开始搜索节点的下标 * param {*} y 开始搜索节点的下标 * return {*} */ const dfs (graph, x, y) { if (graph[x][y] ! 1) return graph[x][y] 2 // 标记为非孤岛陆地 for (let i 0; i 4; i) { let nextx x dir[i][0] let nexty y dir[i][1] if (nextx 0 || nextx N || nexty 0 || nexty M) continue dfs(graph, nextx, nexty) } } (async function () { // 读取输入初始化地图 await initGraph() // 遍历地图左右两边 for (let i 0; i N; i) { if (graph[i][0] 1) dfs(graph, i, 0) if (graph[i][M - 1] 1) dfs(graph, i, M - 1) } // 遍历地图上下两边 for (let j 0; j M; j) { if (graph[0][j] 1) dfs(graph, 0, j) if (graph[N - 1][j] 1) dfs(graph, N - 1, j) } // 遍历地图将孤岛沉没即将陆地1标记为0将非孤岛陆地2标记为1 for (let i 0; i N; i) { for (let j 0; j M; j) { if (graph[i][j] 1) graph[i][j] 0 else if (graph[i][j] 2) graph[i][j] 1 } console.log(graph[i].join( )); } })() #bfsconst r1 require(readline).createInterface({ input: process.stdin }); // 创建readline接口 let iter r1[Symbol.asyncIterator](); // 创建异步迭代器 const readline async () (await iter.next()).value; let graph // 地图 let N, M // 地图大小 const dir [[0, 1], [1, 0], [0, -1], [-1, 0]] //方向 // 读取输入初始化地图 const initGraph async () { let line await readline(); [N, M] line.split( ).map(Number); graph new Array(N).fill(0).map(() new Array(M).fill(0)) for (let i 0; i N; i) { line await readline() line line.split( ).map(Number) for (let j 0; j M; j) { graph[i][j] line[j] } } } /** * description: 从xy开始广度优先遍历地图 * param {*} graph 地图 * param {*} x 开始搜索节点的下标 * param {*} y 开始搜索节点的下标 * return {*} */ const bfs (graph, x, y) { let queue [] queue.push([x, y]) graph[x][y] 2 // 标记为非孤岛陆地 while (queue.length) { let [xx, yy] queue.shift() for (let i 0; i 4; i) { let nextx xx dir[i][0] let nexty yy dir[i][1] if (nextx 0 || nextx N || nexty 0 || nexty M) continue if (graph[nextx][nexty] 1) bfs(graph, nextx, nexty) } } } (async function () { // 读取输入初始化地图 await initGraph() // 遍历地图左右两边 for (let i 0; i N; i) { if (graph[i][0] 1) bfs(graph, i, 0) if (graph[i][M - 1] 1) bfs(graph, i, M - 1) } // 遍历地图上下两边 for (let j 0; j M; j) { if (graph[0][j] 1) bfs(graph, 0, j) if (graph[N - 1][j] 1) bfs(graph, N - 1, j) } // 遍历地图将孤岛沉没即将陆地1标记为0将非孤岛陆地2标记为1 for (let i 0; i N; i) { for (let j 0; j M; j) { if (graph[i][j] 1) graph[i][j] 0 else if (graph[i][j] 2) graph[i][j] 1 } console.log(graph[i].join( )); } })()水流问题题目描述现有一个 N × M 的矩阵每个单元格包含一个数值这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界而矩阵的右边界和下边界被视为第二组边界。矩阵模拟了一个地形当雨水落在上面时水会根据地形的倾斜向低处流动但只能从较高或等高的地点流向较低或等高并且相邻上下左右方向的地点。我们的目标是确定那些单元格从这些单元格出发的水可以达到第一组边界和第二组边界。输入描述第一行包含两个整数 N 和 M分别表示矩阵的行数和列数。后续 N 行每行包含 M 个整数表示矩阵中的每个单元格的高度。输出描述输出共有多行每行输出两个整数用一个空格隔开表示可达第一组边界和第二组边界的单元格的坐标输出顺序任意。输入示例5 5 1 3 1 2 4 1 2 1 3 2 2 4 7 2 1 4 5 6 1 1 1 4 1 2 1输出示例0 4 1 3 2 2 3 0 3 1 3 2 4 0 4 1提示信息图中的蓝色方块上的雨水既能流向第一组边界也能流向第二组边界。所以最终答案为所有蓝色方块的坐标。数据范围1 M, N 50思路我们可以先从第一组边界上的节点逆流而上将遍历过的节点全部标记上然后再从第二组边界出发进行同样的操作双方都标记过的节点就是既可以流向第一组边界又可以流向第二组边界的节点。如图有红又有绿的就是我们要求的节点代码示例const r1 require(readline).createInterface({ input: process.stdin }); // 创建readline接口 let iter r1[Symbol.asyncIterator](); // 创建异步迭代器 const readline async () (await iter.next()).value; let graph // 地图 let N, M // 地图大小 const dir [[0, 1], [1, 0], [0, -1], [-1, 0]] //方向 // 读取输入初始化地图 const initGraph async () { let line await readline(); [N, M] line.split( ).map(Number); graph new Array(N).fill(0).map(() new Array(M).fill(0)) for (let i 0; i N; i) { line await readline() line line.split( ).map(Number) for (let j 0; j M; j) { graph[i][j] line[j] } } } /** * description: 从xy开始深度优先遍历地图 * param {*} graph 地图 * param {*} visited 可访问节点 * param {*} x 开始搜索节点的下标 * param {*} y 开始搜索节点的下标 * return {*} */ const dfs (graph, visited, x, y) { if (visited[x][y]) return visited[x][y] true // 标记为可访问 for (let i 0; i 4; i) { let nextx x dir[i][0] let nexty y dir[i][1] if (nextx 0 || nextx N || nexty 0 || nexty M) continue //越界,跳过 if (graph[x][y] graph[nextx][nexty]) continue //不能流过.跳过 dfs(graph, visited, nextx, nexty) } } /** * description: 判断地图上的(x, y)是否可以到达第一组边界和第二组边界 * param {*} x 坐标 * param {*} y 坐标 * return {*} true可以到达false不可以到达 */ const isResult (x, y) { let visited new Array(N).fill(false).map(() new Array(M).fill(false)) let isFirst false //是否可到达第一边界 let isSecond false //是否可到达第二边界 // 深搜将(x, y)可到达的所有节点做标记 dfs(graph, visited, x, y) // 判断能否到第一边界左边 for (let i 0; i N; i) { if (visited[i][0]) { isFirst true break } } // 判断能否到第一边界上边 for (let j 0; j M; j) { if (visited[0][j]) { isFirst true break } } // 判断能否到第二边界右边 for (let i 0; i N; i) { if (visited[i][M - 1]) { isSecond true break } } // 判断能否到第二边界下边 for (let j 0; j M; j) { if (visited[N - 1][j]) { isSecond true break } } return isFirst isSecond } (async function () { // 读取输入初始化地图 await initGraph() // 遍历地图判断是否能到达第一组边界和第二组边界 for (let i 0; i N; i) { for (let j 0; j M; j) { if (isResult(i, j)) console.log(i j); } } })()建造最大岛屿题目描述给定一个由 1陆地和 0水组成的矩阵你最多可以将矩阵中的一格水变为一块陆地在执行了此操作之后矩阵中最大的岛屿面积是多少。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。输入描述第一行包含两个整数 N, M表示矩阵的行数和列数。之后 N 行每行包含 M 个数字数字为 1 或者 0表示岛屿的单元格。输出描述输出一个整数表示最大的岛屿面积。输入示例4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1输出示例6提示信息对于上面的案例有两个位置可将 0 变成 1使得岛屿的面积最大即 6。数据范围1 M, N 50。思路本题的暴力解法是将每一个0改成1但是其实我们只需要用一次dfs把每个岛屿的面积记录下来就好然后遍历所有0的方格把0变成1然后统计该10变成的1周边岛屿面具将相邻面积加起来遍历所有0之后就可以得到一个选一个0变成1之后的最大面积。代码示例const r1 require(readline).createInterface({ input: process.stdin }); // 创建readline接口 let iter r1[Symbol.asyncIterator](); // 创建异步迭代器 const readline async () (await iter.next()).value; let graph // 地图 let N, M // 地图大小 let visited // 访问过的节点, 标记岛屿 const dir [[0, 1], [1, 0], [0, -1], [-1, 0]] //方向 let count 0 // 统计岛屿面积 let areaMap new Map() // 存储岛屿面积 // 读取输入初始化地图 const initGraph async () { let line await readline(); [N, M] line.split( ).map(Number); graph new Array(N).fill(0).map(() new Array(M).fill(0)) visited new Array(N).fill(0).map(() new Array(M).fill(0)) for (let i 0; i N; i) { line await readline() line line.split( ).map(Number) for (let j 0; j M; j) { graph[i][j] line[j] } } } /** * description: 从xy开始深度优先遍历地图 * param {*} graph 地图 * param {*} visited 可访问节点 * param {*} x 开始搜索节点的下标 * param {*} y 开始搜索节点的下标 * param {*} mark 当前岛屿的标记 * return {*} */ const dfs (graph, visited, x, y, mark) { if (visited[x][y] ! 0) return visited[x][y] mark count for (let i 0; i 4; i) { let nextx x dir[i][0] let nexty y dir[i][1] if (nextx 0 || nextx N || nexty 0 || nexty M) continue //越界, 跳过 // 已访问过, 或者是海洋, 跳过 if (visited[nextx][nexty] ! 0 || graph[nextx][nexty] 0) continue dfs(graph, visited, nextx, nexty, mark) } } (async function () { // 读取输入初始化地图 await initGraph() let isAllLand true //标记整个地图都是陆地 let mark 2 // 标记岛屿 for (let i 0; i N; i) { for (let j 0; j M; j) { if (graph[i][j] 0 isAllLand) isAllLand false if (graph[i][j] 1 visited[i][j] 0) { count 0 dfs(graph, visited, i, j, mark) areaMap.set(mark, count) mark } } } // 如果全是陆地, 直接返回面积 if (isAllLand) { console.log(N * M); return } let result 0 // 记录最后结果 let visitedIsland new Map() //标记访问过的岛屿, 因为海洋四周可能是同一个岛屿, 需要标记避免重复统计面积 for (let i 0; i N; i) { for (let j 0; j M; j) { if (visited[i][j] 0) { count 1 // 记录连接之后的岛屿数量 visitedIsland.clear() // 每次使用时清空 // 计算海洋周围岛屿面积 for (let m 0; m 4; m) { const nextx i dir[m][0] const nexty j dir[m][1] if (nextx 0 || nextx N || nexty 0 || nexty M) continue //越界, 跳过 const island visited[nextx][nexty] if (island 0 || visitedIsland.get(island)) continue// 四周是海洋或者访问过的陆地 跳过 // 标记为访问, 计算面积 visitedIsland.set(island, true) count areaMap.get(visited[nextx][nexty]) } result Math.max(result, count) } } } console.log(result); })()