孤岛计数
深搜版文章讲解/视频讲解
广搜版文章讲解/视频讲解
题目描述：
给定一个由 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输出示例：
3
提示信息
根据测试案例中所展示，岛屿数量共有 3 个，所以输出 3。
数据范围：
- 1 <= N, M <= 50
思路：
本题中的每座岛屿都只能由水平方向和/或竖直方向上相邻的陆地连接形成，也就是说斜角度的连接是不算数的，如图，这是三个岛屿：
那么思路就是遇到一个没有遍历过的节点陆地，就让计数器加一，然后把节点陆地所能遍历到的陆地全部标记上。如果遇到了标记过的陆地节点和海洋节点就直接跳过，这样计数器就是最终岛屿的数量，所以我们本题标记所有陆地节点能遍历到的陆地的方式就可以选择dfs和bfs了。
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 visited let result = 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)) visited = new Array(N).fill(false).map(() => new Array(M).fill(false)) 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) => { for (let i = 0; i < 4; i++) { const nextx = x + dir[i][0] const nexty = y + dir[i][1] if (nextx < 0 || nextx >= N || nexty < 0 || nexty >= M) continue if (!visited[nextx][nexty] && graph[nextx][nexty] === 1) { visited[nextx][nexty] = true dfs(graph, visited, nextx, nexty) } } } (async function () { // 读取输入，初始化地图 await initGraph() // 统计岛屿数 for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { if (!visited[i][j] && graph[i][j] === 1) { // 标记已访问 visited[i][j] = true // 遇到没访问过的陆地，+1 result++ // 深度优先遍历，将相邻陆地标记为已访问 dfs(graph, visited, i, j) } } } console.log(result); })()bfs有一个值得注意的点，只要是加入队列就代表走过了，就需要标记，而不是从队列拿出来的时候再去标记走过，如果从队列拿出结点再标记，就会出现以下情况，导致节点重复加入队列：
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 visited let result = 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)) visited = new Array(N).fill(false).map(() => new Array(M).fill(false)) 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 bfs = (graph, visited, x, y) => { let queue = [] queue.push([x, y]) visited[x][y] = true //只要加入队列就立刻标记为访问过 while (queue.length) { let [x, y] = queue.shift() 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] && graph[nextx][nexty] === 1){ queue.push([nextx, nexty]) visited[nextx][nexty] = true } } } } (async function () { // 读取输入，初始化地图 await initGraph() // 统计岛屿数 for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { if (!visited[i][j] && graph[i][j] === 1) { // 遇到没访问过的陆地，+1 result++ // 广度优先遍历，将相邻陆地标记为已访问 bfs(graph, visited, i, j) } } } console.log(result); })()最大岛屿的面积
文章讲解/视频讲解
题目描述
给定一个由 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输出示例
4
提示信息
样例输入中，岛屿的最大面积为 4。
数据范围：
- 1 <= M, N <= 50。
思路：
本题还是dfs与bfs的基础类题目，就是去搜索每个岛屿上‘1’的数量，然后取一个最大的
dfs：两种写法，要么dfs处理当前节点的相邻节点，即主函数遇到岛屿就计数为1，由dfs来处理接下来的相邻陆地。还有一种写法是dfs处理当前节点，即主函数遇到岛屿计数为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 visited // 访问过的节点 let result = 0 // 最大岛屿面积 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)) visited = new Array(N).fill(false).map(() => new Array(M).fill(false)) 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) => { 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] && graph[nextx][nexty] === 1){ count++ visited[nextx][nexty] = true dfs(graph, visited, nextx, nexty) } } } (async function () { // 读取输入，初始化地图 await initGraph() // 统计最大岛屿面积 for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { if (!visited[i][j] && graph[i][j] === 1) { //遇到没有访问过的陆地 // 重新计算面积 count = 1 visited[i][j] = true // 深度优先遍历，统计岛屿内节点数，并将岛屿标记为已访问 dfs(graph, visited, i, j) // 更新最大岛屿面积 result = Math.max(result, count) } } } console.log(result); })()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 visited // 访问过的节点 let result = 0 // 最大岛屿面积 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)) visited = new Array(N).fill(false).map(() => new Array(M).fill(false)) 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 bfs = (graph, visited, x, y) => { let queue = [] queue.push([x, y]) count++ visited[x][y] = true //只要加入队列就立刻标记为访问过 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(!visited[nextx][nexty] && graph[nextx][nexty] === 1){ queue.push([nextx, nexty]) count++ visited[nextx][nexty] = true } } } } (async function () { // 读取输入，初始化地图 await initGraph() // 统计最大岛屿面积 for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { if (!visited[i][j] && graph[i][j] === 1) { //遇到没有访问过的陆地 // 重新计算面积 count = 0 // 广度优先遍历，统计岛屿内节点数，并将岛屿标记为已访问 bfs(graph, visited, i, j) // 更新最大岛屿面积 result = Math.max(result, count) } } } console.log(result); })()这些题都是思路比较简单，难点都在dfs和bfs的理论基础上
