制作網(wǎng)站品牌公司哪家好,網(wǎng)站出現(xiàn) 503怎么了,wordpress臨時關站,亞馬遜一般在哪些網(wǎng)站上做推廣孤島計數(shù) 深搜版文章講解/視頻講解 廣搜版文章講解/視頻講解 題目描述#xff1a; 給定一個由 1#xff08;陸地#xff09;和 0#xff08;水#xff09;組成的矩陣#xff0c;你需要計算島嶼的數(shù)量。島嶼由水平方向或垂直方向上相鄰的陸地連接而成#xff0c;并且…孤島計數(shù)深搜版文章講解/視頻講解廣搜版文章講解/視頻講解題目描述給定一個由 1陸地和 0水組成的矩陣你需要計算島嶼的數(shù)量。島嶼由水平方向或垂直方向上相鄰的陸地連接而成并且四周都是水域。你可以假設矩陣外均被水包圍。輸入描述第一行包含兩個整數(shù) N, M表示矩陣的行數(shù)和列數(shù)。后續(xù) N 行每行包含 M 個數(shù)字數(shù)字為 1 或者 0。輸出描述輸出一個整數(shù)表示島嶼的數(shù)量。如果不存在島嶼則輸出 0。輸入示例4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1輸出示例3提示信息根據(jù)測試案例中所展示島嶼數(shù)量共有 3 個所以輸出 3。數(shù)據(jù)范圍1 N, M 50思路本題中的每座島嶼都只能由水平方向和/或豎直方向上相鄰的陸地連接形成也就是說斜角度的連接是不算數(shù)的如圖這是三個島嶼那么思路就是遇到一個沒有遍歷過的節(jié)點陸地就讓計數(shù)器加一然后把節(jié)點陸地所能遍歷到的陸地全部標記上。如果遇到了標記過的陸地節(jié)點和海洋節(jié)點就直接跳過這樣計數(shù)器就是最終島嶼的數(shù)量所以我們本題標記所有陸地節(jié)點能遍歷到的陸地的方式就可以選擇dfs和bfs了。dfs代碼示例const r1 require(readline).createInterface({ input: process.stdin }); // 創(chuàng)建readline接口 let iter r1[Symbol.asyncIterator](); // 創(chuàng)建異步迭代器 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: 從節(jié)點x,y開始深度優(yōu)先遍歷 * param {*} graph 是地圖也就是一個二維數(shù)組 * param {*} visited 標記訪問過的節(jié)點不要重復訪問 * param {*} x 表示開始搜索節(jié)點的下標 * param {*} y 表示開始搜索節(jié)點的下標 * 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() // 統(tǒng)計島嶼數(shù) 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 // 遇到?jīng)]訪問過的陸地1 result // 深度優(yōu)先遍歷將相鄰陸地標記為已訪問 dfs(graph, visited, i, j) } } } console.log(result); })()bfs有一個值得注意的點只要是加入隊列就代表走過了就需要標記而不是從隊列拿出來的時候再去標記走過如果從隊列拿出結點再標記就會出現(xiàn)以下情況導致節(jié)點重復加入隊列bfs代碼示例const r1 require(readline).createInterface({ input: process.stdin }); // 創(chuàng)建readline接口 let iter r1[Symbol.asyncIterator](); // 創(chuàng)建異步迭代器 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)開始廣度優(yōu)先遍歷 * param {*} graph 地圖 * param {*} visited 訪問過的節(jié)點 * param {*} x 開始搜索節(jié)點的下標 * param {*} y 開始搜索節(jié)點的下標 * 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() // 統(tǒng)計島嶼數(shù) for (let i 0; i N; i) { for (let j 0; j M; j) { if (!visited[i][j] graph[i][j] 1) { // 遇到?jīng)]訪問過的陸地1 result // 廣度優(yōu)先遍歷將相鄰陸地標記為已訪問 bfs(graph, visited, i, j) } } } console.log(result); })()最大島嶼的面積文章講解/視頻講解題目描述給定一個由 1陸地和 0水組成的矩陣計算島嶼的最大面積。島嶼面積的計算方式為組成島嶼的陸地的總數(shù)。島嶼由水平方向或垂直方向上相鄰的陸地連接而成并且四周都是水域。你可以假設矩陣外均被水包圍。輸入描述第一行包含兩個整數(shù) N, M表示矩陣的行數(shù)和列數(shù)。后續(xù) N 行每行包含 M 個數(shù)字數(shù)字為 1 或者 0表示島嶼的單元格。輸出描述輸出一個整數(shù)表示島嶼的最大面積。如果不存在島嶼則輸出 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。數(shù)據(jù)范圍1 M, N 50。思路本題還是dfs與bfs的基礎類題目就是去搜索每個島嶼上‘1’的數(shù)量然后取一個最大的dfs兩種寫法要么dfs處理當前節(jié)點的相鄰節(jié)點即主函數(shù)遇到島嶼就計數(shù)為1由dfs來處理接下來的相鄰陸地。還有一種寫法是dfs處理當前節(jié)點即主函數(shù)遇到島嶼計數(shù)為0dfs處理的是接下來全部的陸地這里我是用解法一const r1 require(readline).createInterface({ input: process.stdin }); // 創(chuàng)建readline接口 let iter r1[Symbol.asyncIterator](); // 創(chuàng)建異步迭代器 const readline async () (await iter.next()).value; let graph // 地圖 let N, M // 地圖大小 let visited // 訪問過的節(jié)點 let result 0 // 最大島嶼面積 let count 0 // 島嶼內(nèi)節(jié)點數(shù) 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)開始深度優(yōu)先遍歷 * param {*} graph 地圖 * param {*} visited 訪問過的節(jié)點 * param {*} x 開始搜索節(jié)點的下標 * param {*} y 開始搜索節(jié)點的下標 * 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() // 統(tǒng)計最大島嶼面積 for (let i 0; i N; i) { for (let j 0; j M; j) { if (!visited[i][j] graph[i][j] 1) { //遇到?jīng)]有訪問過的陸地 // 重新計算面積 count 1 visited[i][j] true // 深度優(yōu)先遍歷統(tǒng)計島嶼內(nèi)節(jié)點數(shù)并將島嶼標記為已訪問 dfs(graph, visited, i, j) // 更新最大島嶼面積 result Math.max(result, count) } } } console.log(result); })()bfs就直接一種寫法const r1 require(readline).createInterface({ input: process.stdin }); // 創(chuàng)建readline接口 let iter r1[Symbol.asyncIterator](); // 創(chuàng)建異步迭代器 const readline async () (await iter.next()).value; let graph // 地圖 let N, M // 地圖大小 let visited // 訪問過的節(jié)點 let result 0 // 最大島嶼面積 let count 0 // 島嶼內(nèi)節(jié)點數(shù) 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)開始廣度優(yōu)先遍歷 * param {*} graph 地圖 * param {*} visited 訪問過的節(jié)點 * param {*} x 開始搜索節(jié)點的下標 * param {*} y 開始搜索節(jié)點的下標 * 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() // 統(tǒng)計最大島嶼面積 for (let i 0; i N; i) { for (let j 0; j M; j) { if (!visited[i][j] graph[i][j] 1) { //遇到?jīng)]有訪問過的陸地 // 重新計算面積 count 0 // 廣度優(yōu)先遍歷統(tǒng)計島嶼內(nèi)節(jié)點數(shù)并將島嶼標記為已訪問 bfs(graph, visited, i, j) // 更新最大島嶼面積 result Math.max(result, count) } } } console.log(result); })()這些題都是思路比較簡單難點都在dfs和bfs的理論基礎上