当前位置：首页 > news >正文

打卡52天------图论(应用题)

news 来源：原创 2024/9/19 11:07:42

一、孤岛的总面积

基础题目可以自己尝试做一做。

代码随想录

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) returngraph[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) continuedfs(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);
})()

二、沉没孤岛

和上一题差不多，尝试自己做做

代码随想录

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) returngraph[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) continuedfs(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标记为1for (let i = 0; i < N; i++) {for (let j = 0; j < M; j++) {if (graph[i][j] === 1) graph[i][j] = 0else if (graph[i][j] === 2) graph[i][j] = 1}console.log(graph[i].join(' '));}
})()

三、水流问题

需要点优化思路，建议先自己读题，相处一个解题方法，有时间就自己写代码，没时间就直接看题解，优化方式会让你耳目一新。

代码随想录

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]) returnvisited[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 = truebreak}}// 判断能否到第一边界上边for (let j = 0; j < M; j++) {if (visited[0][j]) {isFirst = truebreak}}// 判断能否到第二边界右边for (let i = 0; i < N; i++) {if (visited[i][M - 1]) {isSecond = truebreak}}// 判断能否到第二边界下边for (let j = 0; j < M; j++) {if (visited[N - 1][j]) {isSecond = truebreak}}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);}}
})()