c-使用二维阵列进行BFS

Question

我有一个网格，用于保存值为1和0的单元格(它们是随机生成的(。值为1的单元格表示它是一个空单元格，我可以移动到该单元格，值为0表示该单元格被阻止。我希望每个位置(x，y(都能通过向所有4个方向移动而不是对角移动来判断是否有到点(x'，y'(的可用路径。

从一项研究来看，我的问题的解决方案是BFS算法，但我很难理解我们如何将数组转换为图，以及我们如何保留阻塞单元格的信息。

Answer 1

BFS的一般结构如下：

1. 创建一个队列
2. 登记根节点
3. 虽然队列不是空的，
   1. 取消节点的队列
   2. 访问节点
   3. 将节点的子节点排队

此处应用

1. 创建一个队列
2. 创建visited，一个每个单元都有一个位的数组
3. 对于每一行CCD_ 2，
   1. 对于每个列CCD_ 3，
      1. 如果小区(x、y(具有值1，
         1. 设置单元(x、y(的visited位
      2. 否则，
         1. 清除单元(x、y(的visited位
4. 将点(x，y(排队
5. 虽然队列不是空的，
   1. 对点(x2、y2(进行排队
   2. 如果没有设置用于小区的visited比特(x2、y2(，
      1. 设置单元(x2、y0(的visited位
      2. 如果点(x2，y2(等于(x’，y’(，
         1. 返回true
      3. 对于与小区(x2、y2(相邻的每个小区，
         1. 对该单元格的坐标进行排队
6. 返回false

(它不一定是位数组。它只需要提供快速查找和插入。例如，可以使用某种形式的关联数组。位向量似乎最适合我。(

---

但这并不完全正确。你不想简单地检查两个单元格是否连接，你想知道哪个单元格连接到哪个单元格。对每个单元格组合执行上述搜索将非常缓慢。以下内容可避免重复工作：

1. 创建一个队列
2. 创建groups，一个数组，每个单元格都有一个整数
   该整数必须足够大，可以容纳单元格数加2。
   VOID表示该整数可以取的最大值
   TODO是指该整数可以取的最大值，减去1
3. 对于每一行CCD_ 28，
   1. 对于每个列CCD_ 29，
      1. 如果小区(x0、y(具有值1，
         1. 将groups中单元格(x、y(的整数设置为TODO
      2. 否则，
         1. 将groups中单元格(x、y(的整数设置为VOID
4. 将group_id设置为0
5. 对于每一行CCD_ 43，
   1. 对于每个列CCD_ 44，如果小区(x、y(的组是TODO，
      1. 对点(x、y(进行排队。
         1. 当队列不是空的时，
            1. 出列点(x2、y2(
            2. 如果小区(x2、y2(的组是TODO，
               1. 将单元(x2、y2(的组设置为group_id
               2. 对于与小区(x2、y2(相邻的每个小区，
                  1. 对该单元格的坐标进行排队
      2. 递增group_id

执行此操作后，每个单元格都将连接到groups中具有相同值的其他单元格。

(同样，使用的确切数据结构具有灵活性。(

---

下面是一个示例实现。和上面一样，它仍然不在C中。重点是解释一种可以使用的方法，但实际的C实现留给用户。

输入：

use POSIX qw( ceil );
my $num_rows = ...;
my $num_cols = ...;
my $n = $y * $num_cols + $x;
my $cells = "" x ceil( $n / 8 );   # A string of `$n` bits.
# Initialize cells here.
for ( ... ) {
my $y = ...;
my $x = ...;
vec( $cells, $y * $num_cols + $x, 1 ) = 1;  # Sets a bit.
}

算法：

my $visited = ~.$cells;   # String bitwise negation.
my @groups;   # This is going to be an array of arrays.
for my $i ( 0 .. $n-1 ) {
next if vec( $visited, $i, 1 );
my $group = [ ];
push @groups, $group;
my @to_visit = $i;   # Our queue (or stack).
while ( @to_visit ) {
my $j = shift( @to_visit );   # Use `pop` for DFS.
next if vec( $visited, $j, 1 );
vec( $visited, $j, 1 ) = 1;
push @$group, $j;
my $y2 = int( $j / $num_cols );
my $x2 =      $j % $num_cols;
for my $dy ( ( $y2 == 0 ? () : -1 ), ( $y2 == $num_rows-1 ? () : +1 ) ) {
for my $dx ( ( $x2 == 0 ? () : -1 ), ( $x2 == $num_cols-1 ? () : +1 ) ) {
push @to_visit, ( $y2 + $dy ) * $cols + ( $x2 + $dx );
}}
}
}

输出：

use Data::Dumper qw( Dumper );
print( Dumper( @groups ) );

---

最后，请注意DFS和BFS一样工作。使用DFS的实现将是相同的，只是队列将被堆栈替换。