#!/usr/bin/perl -w

use strict;

my (%visited);

my ($word) = "";

my (@board) = (
    ['a','b','c','d'],
    ['e','f','g','h'],
    ['i','j','k','l'],
    ['m','n','o','p']
);

my (@moves) = (
    [0, -1], #x + 0, y + -1
    [1, -1],
    [1, 0],
    [1, 1],
    [0, 1],
    [-1, 1],
    [-1, 0],
    [-1, 1]
);

dfs(0, 0, %visited, $word);

sub dfs {
    my ($x, $y, %visited, $word) = @_;
    my ($end) = 1; # end is used to determine if there are anymore characters in the string before printing $word

    $visited{$x . $y}++;
    $word .= $board[$y][$x];
    foreach (@moves) {
        next if
            $x + $$_[0] < 0 or
            $x + $$_[0] > 3 or
            $y + $$_[1] < 0 or
            $y + $$_[1] > 3 or
            exists $visited{
                ($x + $$_[0]) . ($y + $$_[1])
            }; #make sure the transformed coordinates are valid and new
        $end = 0;
        dfs($x + $$_[0], $y + $$_[1], %visited, $word);
    }
    print $word if $end == 1;
}