|
|
| Line 1: |
Line 1: |
| − | Consider the following example:
| + | #REDIRECT [[UNTV]] |
| − | | |
| − | {|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";
| |
