Difference between revisions of "TADM2E 8.17"

From Algorithm Wiki
Jump to: navigation, search
(Blanked the page)
(Undo revision 1088 by FuckMatt (talk))
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
Consider the following example:
  
 +
{|border="1"
 +
|G||G||G||G
 +
|-
 +
|G||B||G||G
 +
|-
 +
|G||G||G||G
 +
|}
 +
 +
There are four possible routes that avoid the bad intersection at (1, 1): DDRRR, RRDDR, RRDRD and RRRDD.  We can start at the top-left and fill each square with the possible number of routes that lead to it:
 +
 +
{|border="1"
 +
|1||?||?||?
 +
|-
 +
|?||B||?||?
 +
|-
 +
|?||?||?||?
 +
|}
 +
 +
 +
{|border="1"
 +
|1||1||?||?
 +
|-
 +
|1||B||?||?
 +
|-
 +
|?||?||?||?
 +
|}
 +
 +
 +
{|border="1"
 +
|1||1||1||?
 +
|-
 +
|1||B||?||?
 +
|-
 +
|1||?||?||?
 +
|}
 +
 +
 +
{|border="1"
 +
|1||1||1||1
 +
|-
 +
|1||B||1||?
 +
|-
 +
|1||1||?||?
 +
|}
 +
 +
 +
{|border="1"
 +
|1||1||1||1
 +
|-
 +
|1||B||1||2
 +
|-
 +
|1||1||2||?
 +
|}
 +
 +
 +
{|border="1"
 +
|1||1||1||1
 +
|-
 +
|1||B||1||2
 +
|-
 +
|1||1||2||4
 +
|}
 +
 +
Implementation in Perl:
 +
 +
#!/usr/bin/perl
 +
 +
use warnings;
 +
use strict;
 +
 +
sub count_paths
 +
  {
 +
  my @bad = @_;
 +
 +
  my $nr = @bad;
 +
  my $nc = @{$bad[0]};
 +
 +
  my @paths = map { [ map { 0 } @{$bad[0]} ] } @bad;
 +
 +
  for my $r (0 .. $nr - 1)
 +
    {
 +
    for my $c (0 .. $nc - 1)
 +
      {
 +
      next if $bad[$r][$c];
 +
 +
      my $np = $r == 0 && $c == 0 ? 1 : 0;
 +
 +
      $np += $paths[$r - 1][$c]    if $r > 0 && !$bad[$r - 1][$c];
 +
      $np += $paths[$r]    [$c - 1] if $c > 0 && !$bad[$r]    [$c - 1];
 +
 +
      $paths[$r][$c] = $np;
 +
      }
 +
    }
 +
 +
  return $paths[$nr - 1][$nc - 1];
 +
  }
 +
 +
my @bad = ( [0,0,0,0], [0,1,0,0], [0,0,0,0]);
 +
 +
my $np = count_paths @bad;
 +
 +
print $np, "\n";

Latest revision as of 00:49, 1 August 2020

Consider the following example:

G G G G
G B G G
G G G G

There are four possible routes that avoid the bad intersection at (1, 1): DDRRR, RRDDR, RRDRD and RRRDD. We can start at the top-left and fill each square with the possible number of routes that lead to it:

1 ? ? ?
? B ? ?
? ? ? ?


1 1 ? ?
1 B ? ?
? ? ? ?


1 1 1 ?
1 B ? ?
1 ? ? ?


1 1 1 1
1 B 1 ?
1 1 ? ?


1 1 1 1
1 B 1 2
1 1 2 ?


1 1 1 1
1 B 1 2
1 1 2 4

Implementation in Perl: 

#!/usr/bin/perl

use warnings;
use strict;

sub count_paths
  {
  my @bad = @_;

  my $nr = @bad;
  my $nc = @{$bad[0]};

  my @paths = map { [ map { 0 } @{$bad[0]} ] } @bad;

  for my $r (0 .. $nr - 1)
    {
    for my $c (0 .. $nc - 1)
      {
      next if $bad[$r][$c];

      my $np = $r == 0 && $c == 0 ? 1 : 0;

      $np += $paths[$r - 1][$c]     if $r > 0 && !$bad[$r - 1][$c];
      $np += $paths[$r]    [$c - 1] if $c > 0 && !$bad[$r]    [$c - 1];

      $paths[$r][$c] = $np;
      }
    }

  return $paths[$nr - 1][$nc - 1];
  }

my @bad = ( [0,0,0,0], [0,1,0,0], [0,0,0,0]);

my $np = count_paths @bad;

print $np, "\n";
Retrieved from "https://algorist.com/algowiki_v2/index.php?title=TADM2E_8.17&oldid=1109"