Category Archives: php

After the Dance Battle

php

This question was given by Facebook Hacker Cup Round 01 in 2010. Let’s see the question and the solution with php.

After the Dance Battle

Walking home in triumph after a particularly satisfying dance battle, you take a wrong turn into an alley and find yourself presented with a perplexing puzzle. The entrance to the alley behind you disappears and you are faced with a rectangular grid of colorful squares, with thick granite walls occupying some of the squares. The grid is recessed far enough into the ground that, from above, you can see the exit in the distance and the layout of all the colors. You can memorize the entire layout before entering the grid and trying to make your way across.

As you stand above the grid trying to commit its layout to memory, you notice something strange about the urban wildlife trapped with you in the maze; the various fauna seem to be able to move almost instantaneously between squares of the same color. You suspect that you can use this property to your advantage, which you attempt to keep at the front of your mind as you enter the labyrinth with your intentions set on getting out as quickly as possible.

Input

Your input file will consist of a number N followed by some whitespace and then N test cases. Each case consists of two numbers R and C, the number of rows and columns in the maze, followed by R strings describing the layout of the rows in order. All tokens are whitespace-separated.

Each element describing a row will consist of the characters ‘S’, ‘E’, ‘W’, or the digits 0-9. There will be only one ‘S’ square and one ‘E’ square, ‘S’ being your starting point and ‘E’ being the exit. ‘S’ will be in the first row, ‘E’ will be in the last row. ‘W’ squares are occupied by walls, and cannot be entered. Digits 1-9 represent the colors of the squares. You can pass in a single step between adjacent squares or between any two squares of the same color. The start and exit points as well as all ‘0’ squares are inert, i.e., they have no color and must be stepped directly on to or off of. There will always be some valid method of reaching the exit.

Output

Return the number of steps required to reach the exit from the starting point.

Constraints

10 <= N <= 50 2 <= R, C <= 100

Example input
5
5 3 00S 02W 009 W50 E0W
10 6 000S0W 00000W 000WW0 000WWW W0400W 0000WW 0300WW W000WW 0000WW WE0000
15 9 00W0000S0 0000W0000 0WW000000 00W000000 000050000 000080005 050000000 000000000 W0W00W000 00WW0WW00 WWWW00000 0W0090500 WWW0W0000 WW00WW000 0W0WWE000
20 12 40000000S00W 000000000000 03000000000W 100000008000 000000000000 000000700000 000000000700 000000000000 070000000000 000000002070 000100000000 000000000430 000000000000 000004004000 350000000000 W02010000030 W10000000000 000100000300 000009000000 0E0000005000
25 15 0WS00W0W600WWW0 0W6W00WWW0WW0W0 WW0W00W0WW0WWWW W0WW04WWWW0WW0W WW0W0000WWWWWW0 000WWW000WWW9W0 W0WWWW00000WWW0 0WWW0WW0W00WW90 WWW000WW0000WWW W0W000WW0000WWW 0W0800WW0W00000 W000W0W4WW00WWW 000000WW00000WW W000030000304W0 W00000W0000000W W08000000000000 WW00WW00W0W0400 000W0W00300W050 00WWWWWW0WWWW40 00WWWWWWWW00WW0 00WW0000W000WW0 000000000000WWW W602000000W05W0 090000000000W0W WWWWWW000000EW0

Example output

6
11
11
15
13

My Solution in PHP as follows. I used breadth first search.

<?php
if($lines=file('input.txt'))
{
    $cases=trim(array_shift($lines));
    for($k=0 ; $k < $cases; $k++ ) 
    { 
        $g=array(); 
        $clr=array(); 
        $a=preg_split("/[ \s\t]+/",trim($lines[$k])); 
        $r=array_shift($a); 
        $c=array_shift($a); 
        for($j=0; $j < $r ; $j++) 
        { 
            $g[$j]=str_split($a[$j]); 
            foreach($g[$j] as $p => $v)
            {
                if(is_numeric($v) && $v!=0)
                {
                    $clr[$v][]=array($j,$p);
                }
            }
        }
        bfs($g,$clr);
    }
}
function bfs($grid,$colors) // Breadth first search
{
    $steps[0][array_search('S',$grid[0])]=0;
    $q[]=array(0,array_search('S',$grid[0])); //Start node 0
    while(!empty($q))
    {
        $s=array_shift($q);
        $x=$s[0]; $y=$s[1]; //Current point
        $nsteps=$steps[$x][$y]; // Number of steps
        if($grid[$x][$y]=='E')
        {
            echo $nsteps.PHP_EOL;
            return;
        }
        $nebs=array(array($x,$y+1),array($x,$y-1),array($x+1,$y),array($x-1,$y)); //Neighbours
        foreach($nebs as $neb)
        {
            if(isset($grid[$neb[0]][$neb[1]]) && !isset($steps[$neb[0]][$neb[1]]) && $grid[$neb[0]][$neb[1]]!='W')
            {
                $steps[$neb[0]][$neb[1]]=$nsteps+1;
                $q[]=array($neb[0],$neb[1]);
            }
        }
        //Check for color paths
        if(is_array($colors[$grid[$x][$y]]))
        {
            foreach($colors[$grid[$x][$y]] as $color)
            {
                if(!isset($steps[$color[0]][$color[1]]))
                {
                    $steps[$color[0]][$color[1]]=$nsteps+1;
                    $q[]=array($color[0],$color[1]);
                }
            }
        }
    }
}
?>