(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 $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";