/*
    Counting diagonal mazes.
    
    Described in http://www.iwriteiam.nl/D1304.html#17

*/

#include <stdio.h>
#include <stdlib.h>

char maze[1000][1000];
char minsteps[1000][1000];

double rate[100];
int count[100];

int attempts = 0;
int maxsteps = 56;

void search(int steps, double p, int i, int j, char dir)
{
    if (i == 500 && j == 500 && dir == 'd' && steps > 0)
    {
        rate[steps/4] += p;
        count[steps/4]++;
        return;
    }
    
    if (steps == maxsteps)
    {
        attempts++;
        return;
    }

    if (minsteps[i][j] < steps)
        return;
        
    steps++;

    char *mazeij = &maze[i][j];
    char state = *mazeij;
    if (state == ' ')
        p /= 2;
            
    if (dir == 'd')
    {
        if (state == ' ' || state == '1')
        {
            *mazeij = '1';
            search(steps, p, i-1, j, 'l');
            *mazeij = state;
        }
        if (state == ' ' || state == '0')
        {
            *mazeij = '0';
            search(steps, p, i+1, j, 'r');
            *mazeij = state;
        }
    }
    else if (dir == 'u')
    {
        if (state == ' ' || state == '1')
        {
            *mazeij = '1';
            search(steps, p, i+1, j, 'r');
            *mazeij = state;
        }
        if (state == ' ' || state == '0')
        {
            *mazeij = '0';
            search(steps, p, i-1, j, 'l');
            *mazeij = state;
        }
    }
    else if (dir == 'r')
    {
        if (state == ' ' || state == '1')
        {
            *mazeij = '1';
            search(steps, p, i, j-1, 'u');
            *mazeij = state;
        }
        if (state == ' ' || state == '0')
        {
            *mazeij = '0';
            search(steps, p, i, j+1, 'd');
            *mazeij = state;
        }
    }
    else if (dir == 'l')
    {
        if (state == ' ' || state == '1')
        {
            *mazeij = '1';
            search(steps, p, i, j+1, 'd');
            *mazeij = state;
        }
        if (state == ' ' || state == '0')
        {
            *mazeij = '0';
            search(steps, p, i, j-1, 'u');
            *mazeij = state;
        }
    }
}

int main(int argc, char* argv[])
{
    for (int i = 0; i < 999; i++)
        for (int j = 0; j < 999; j++)
        {
            maze[i][j] = ' ';
            minsteps[i][j] = 0;
        }
    maze[500][500] = '1';
    minsteps[500][499] = maxsteps;
    for (int s = maxsteps; s > 0; s = s - 2)
        for (int i = 0; i < 999; i++)
            for (int j = 0; j < 999; j++)
                if (minsteps[i][j] == s)
                {
                    if (minsteps[i+1][j] == 0)
                    {
                        minsteps[i+1][j] = s - 1;
                        if (minsteps[i+1][j-1] == 0)
                            minsteps[i+1][j-1] = s - 2;
                        if (minsteps[i+1][j+1] == 0)
                            minsteps[i+1][j+1] = s - 2;
                    }
                    if (minsteps[i-1][j] == 0)
                    {
                        minsteps[i-1][j] = s - 1;
                        if (minsteps[i-1][j-1] == 0)
                            minsteps[i-1][j-1] = s - 2;
                        if (minsteps[i-1][j+1] == 0)
                            minsteps[i-1][j+1] = s - 2;
                    }
                }
                    
    for (int i = 0; i < 100; i++)
    {
        count[i] = 0;
        rate[i] = 0.0;
    }


    search(0, 1.0, 500, 500, 'd');
    
    for (int i = 1; i < 25; i++)
        printf("%2d %lf\n", 2*i, rate[i]*100);
}