TADM2E 8.17

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