孤岛的总面积
题目描述
给定一个由 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，此时地图为这样：
代码示例：
dfs：
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 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: 从（x，y）开始深度优先遍历地图 * @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); })()bfs：
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 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: 从（x，y）开始广度优先遍历地图 * @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
如图：
代码示例：
dfs
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: 从（x，y）开始深度优先遍历地图 * @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(' ')); } })() #bfs
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: 从（x，y）开始广度优先遍历地图 * @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: 从（x，y）开始深度优先遍历地图 * @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），然后统计该1（0变成的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: 从（x，y）开始深度优先遍历地图 * @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); })()
