#include<stdio.h>

// test

int main (void)
{
    int g[5][5] =
    {
      { 1,0,0,0,0 },
      { 0,0,1,0,0 },
      { 0,1,1,1,1 },
      { 1,0,1,0,0 },
      { 0,0,0,1,0 }
    };
    
    printf("\n 4-way solution = %d \n", mmd4(5,5,g, 2,2));
    printf("\n 8-way solution = %d \n", mmd8(5,5,g, 2,2));
    
    return 0;
}

// 8-way Solution

int mmd8(int h, int w, int g[h][w], int x, int y)
{
    putchar('#');
    return max8(mmd8_up   (h,w,g,x-1,y  ,1),
                mmd8_down (h,w,g,x+1,y  ,1),
                mmd8_left (h,w,g,x  ,y-1,1),
                mmd8_right(h,w,g,x  ,y+1,1),
                
                mmd8_uleft (h,w,g,x-1,y-1,1),
                mmd8_uright(h,w,g,x-1,y+1,1),
                mmd8_dleft (h,w,g,x+1,y-1,1),
                mmd8_dright(h,w,g,x+1,y+1,1));
}

int mmd8_up(int h, int w, int g[h][w], int x, int y, int steps)
{
    if (base_case(h,w,x,y)) return 0;
    putchar('U');
    return max4(g[x][y]?steps:0,
           mmd8_up    (h,w,g,x-1,y  ,steps+1),
           mmd8_uleft (h,w,g,x-1,y-1,steps+1),
           mmd8_uright(h,w,g,x-1,y+1,steps+1));
}

int mmd8_down(int h, int w, int g[h][w], int x, int y, int steps)
{
    if (base_case(h,w,x,y)) return 0;
    putchar('D');
    return max4(g[x][y]?steps:0,
           mmd8_down  (h,w,g,x+1,y  ,steps+1),
           mmd8_dleft (h,w,g,x+1,y-1,steps+1),
           mmd8_dright(h,w,g,x+1,y+1,steps+1));
}

int mmd8_left(int h, int w, int g[h][w], int x, int y, int steps)
{
    if (base_case(h,w,x,y)) return 0;
    putchar('L');
    return max2(g[x][y]?steps:0,
           mmd8_left (h,w,g,x  ,y-1,steps+1),
           mmd8_uleft(h,w,g,x-1,y-1,steps+1),
           mmd8_dleft(h,w,g,x+1,y-1,steps+1));
}

int mmd8_right(int h, int w, int g[h][w], int x, int y, int steps)
{
    if (base_case(h,w,x,y)) return 0;
    putchar('R');
    return max2(g[x][y]?steps:0,
           mmd8_right (h,w,g,x  ,y+1,steps+1),
           mmd8_uright(h,w,g,x-1,y+1,steps+1),
           mmd8_dright(h,w,g,x+1,y+1,steps+1));
}

int mmd8_uleft(int h, int w, int g[h][w], int x, int y, int steps)
{
    if (base_case(h,w,x,y)) return 0;
    putchar('W');
    return max2(g[x][y]?steps:0,
           mmd8_uleft(h,w,g,x-1,y-1,steps+1));
}

int mmd8_uright(int h, int w, int g[h][w], int x, int y, int steps)
{
    if (base_case(h,w,x,y)) return 0;
    putchar('X');
    return max2(g[x][y]?steps:0,
           mmd8_uright(h,w,g,x-1,y+1,steps+1));
}

int mmd8_dleft(int h, int w, int g[h][w], int x, int y, int steps)
{
    if (base_case(h,w,x,y)) return 0;
    putchar('Y');
    return max2(g[x][y]?steps:0,
           mmd8_dleft(h,w,g,x+1,y-1,steps+1));
}

int mmd8_dright(int h, int w, int g[h][w], int x, int y, int steps)
{
    if (base_case(h,w,x,y)) return 0;
    putchar('Z');
    return max2(g[x][y]?steps:0,
           mmd8_dright(h,w,g,x+1,y+1,steps+1));
}

// 4-way Solution

int mmd4(int h, int w, int g[h][w], int x, int y)
{
    putchar('#');
    return max4(mmd_up   (h,w,g,x-1,y  ,1),
                mmd_down (h,w,g,x+1,y  ,1),
                mmd_left (h,w,g,x  ,y-1,1),
                mmd_right(h,w,g,x  ,y+1,1));
}

int mmd_up(int h, int w, int g[h][w], int x, int y, int steps)
{
    if (base_case(h,w,x,y)) return 0;
    putchar('U');
    return max4(g[x][y]?steps:0,
           mmd_up   (h,w,g,x-1,y  ,steps+1),
           mmd_left (h,w,g,x  ,y-1,steps+1),
           mmd_right(h,w,g,x  ,y+1,steps+1));
}

int mmd_down(int h, int w, int g[h][w], int x, int y, int steps)
{
    if (base_case(h,w,x,y)) return 0;
    putchar('D');
    return max4(g[x][y]?steps:0,
           mmd_down (h,w,g,x+1,y  ,steps+1),
           mmd_left (h,w,g,x  ,y-1,steps+1),
           mmd_right(h,w,g,x  ,y+1,steps+1));
}

int mmd_left(int h, int w, int g[h][w], int x, int y, int steps)
{
    if (base_case(h,w,x,y)) return 0;
    putchar('L');
    return max2(g[x][y]?steps:0,
           mmd_left (h,w,g,x  ,y-1,steps+1));
}

int mmd_right(int h, int w, int g[h][w], int x, int y, int steps)
{
    if (base_case(h,w,x,y)) return 0;
    putchar('R');
    return max2(g[x][y]?steps:0,
           mmd_right(h,w,g,x  ,y+1,steps+1));
}

// Utility Functions

int base_case(int h, int w, int x, int y)
{
	if (x < 0) return 1;
	if (y < 0) return 1;
	if (x >= h) return 1;
	if (y >= w) return 1;
    return 0;
}

int max2(int a, int b)
{
    return ((a > b) ? a : b);
}

int max4(int a, int b, int c, int d)
{
    int m = a;
    if (b > m) m = b;
    if (c > m) m = c;
    if (d > m) m = d;
    return m;
}

int max8(int a, int b, int c, int d, int e, int f, int g, int h)
{
    int m = a;
    if (b > m) m = b;
    if (c > m) m = c;
    if (d > m) m = d;
    if (e > m) m = e;
    if (f > m) m = f;
    if (g > m) m = g;
    if (h > m) m = h;
    return m;
}