当前位置：首页 > 文章列表 > Golang > Go教程 > 深入研究：回文和连续块的递归解决方案

深入研究：回文和连续块的递归解决方案

来源：dev.to 2024-09-29 19:06:58 0浏览收藏

本篇文章向大家介绍《深入研究：回文和连续块的递归解决方案》，主要包括，具有一定的参考价值，需要的朋友可以参考一下。

深入研究：回文和连续块的递归解决方案

在本文中，我们将解决 perl weekly challenge #288 中的两项任务：找到最接近的回文并确定矩阵中最大连续块的大小。这两种解决方案都将在 perl 和 go 中递归实现。

连续块

第二个任务是确定给定矩阵中最大连续块的大小，其中所有单元格都包含 x 或 o。

连续块由包含相同符号的元素组成，这些元素与块中的其他元素共享边缘（而不仅仅是角），从而创建一个连接区域。

任务描述

输入： 包含 x 和 o 的矩形矩阵。

输出：最大连续块的大小。

示例

输入：

[
    ['x', 'x', 'x', 'x', 'o'],
    ['x', 'o', 'o', 'o', 'o'],
    ['x', 'o', 'o', 'o', 'o'],
    ['x', 'x', 'x', 'o', 'o'],
]

输出： 11
有一个包含 x 的 9 个连续单元格的块和一个包含 o 的 11 个连续单元格的块。

输入：

[
    ['x', 'x', 'x', 'x', 'x'],
    ['x', 'o', 'o', 'o', 'o'],
    ['x', 'x', 'x', 'x', 'o'],
    ['x', 'o', 'o', 'o', 'o'],
]

输出： 11
有一个包含 x 的 11 个连续单元格的块和一个包含 o 的 9 个连续单元格的块。

输入：

[
    ['x', 'x', 'x', 'o', 'o'],
    ['o', 'o', 'o', 'x', 'x'],
    ['o', 'x', 'x', 'o', 'o'],
    ['o', 'o', 'o', 'x', 'x'],
]

输出： 7
有一个包含 o 的 7 个连续单元格块、另外两个包含 o 的 2 单元格块、三个包含 x 的 2 单元格块和一个包含 x 的 3 单元格块。

解决方案

perl 实现

在此实现中，我们利用递归深度优先搜索（dfs）方法来确定矩阵中最大连续块的大小。主函数初始化一个访问矩阵来跟踪哪些单元已被探索。它迭代每个单元格，每当遇到未访问的单元格时调用递归 dfs 函数。

dfs 函数探索当前单元格的所有四个可能的方向（上、下、左、右）。它通过在共享相同符号且尚未被访问的相邻单元上递归地调用自身来计算连续块的大小。这种递归方法有效地聚合了块的大小，同时确保每个单元仅被计数一次。

sub largest_contiguous_block {
    my ($matrix) = @_;
    my $rows = @$matrix;
    my $cols = @{$matrix->[0]};
    my @visited = map { [(0) x $cols] } 1..$rows;

    my $max_size = 0;

    for my $r (0 .. $rows - 1) {
        for my $c (0 .. $cols - 1) {
            my $symbol = $matrix->[$r][$c];
            my $size = dfs($matrix, \@visited, $r, $c, $symbol);
            $max_size = $size if $size > $max_size;
        }
    }

    return $max_size;
}

sub dfs {
    my ($matrix, $visited, $row, $col, $symbol) = @_;

    return 0 if $row < 0 || $row >= @$matrix || $col < 0 || $col >= @{$matrix->[0]}
                || $visited->[$row][$col] || $matrix->[$row][$col] ne $symbol;

    $visited->[$row][$col] = 1;
    my $count = 1;

    $count += dfs($matrix, $visited, $row + 1, $col, $symbol);
    $count += dfs($matrix, $visited, $row - 1, $col, $symbol);
    $count += dfs($matrix, $visited, $row, $col + 1, $symbol);
    $count += dfs($matrix, $visited, $row, $col - 1, $symbol);

    return $count;
}

实施

go 实现反映了这种递归 dfs 策略。它类似地遍历矩阵并使用递归来探索具有相同符号的连续单元格。

package main

func largestContiguousBlock(matrix [][]rune) int {
    rows := len(matrix)
    if rows == 0 {
        return 0
    }
    cols := len(matrix[0])
    visited := make([][]bool, rows)
    for i := range visited {
        visited[i] = make([]bool, cols)
    }

    maxSize := 0

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            symbol := matrix[r][c]
            size := dfs(matrix, visited, r, c, symbol)
            if size > maxSize {
                maxSize = size
            }
        }
    }

    return maxSize
}

func dfs(matrix [][]rune, visited [][]bool, row, col int, symbol rune) int {
    if row < 0 || row >= len(matrix) || col < 0 || col >= len(matrix[0]) ||
        visited[row][col] || matrix[row][col] != symbol {
        return 0
    }

    visited[row][col] = true
    count := 1

    count += dfs(matrix, visited, row+1, col, symbol)
    count += dfs(matrix, visited, row-1, col, symbol)
    count += dfs(matrix, visited, row, col+1, symbol)
    count += dfs(matrix, visited, row, col-1, symbol)

    return count
}