Difference between revisions of "TADM2E 8.17"
From Algorithm Wiki
(Created page with "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, RR...") |
|
| (5 intermediate revisions by 4 users not shown) | |
(No difference)
| |
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";
