UVa : 11705 (Grasshopper) « Solved Programming Problems

UVa : 11705 (Grasshopper) « Solved Programming Problems:
//用link的Code來釐清題意，之後寫出以下AC Code.

#include <cstdlib>
#include <iostream>


using namespace std;

int g_input[50][50], g_dis[50][50];

char ga[50][50];

int jump(char direct, int y, int x, int row, int col)
{

    if('N' == direct)
    {
        if(y - g_input[y][x] >= 0)
        {

            return g_dis[y - g_input[y][x]][x];
        }

        else return 0;
    }
    else if('W' == direct)
    {
        if(x - g_input[y][x] >= 0)
        {

            return g_dis[y][x - g_input[y][x]];
        }

        else return 0;
    }
    else if('E' == direct)
    {
        if(x + g_input[y][x] < col)
        {

            return g_dis[y][x + g_input[y][x]];
        }

        else return 0;    
    }
    else if('S' == direct)
    {
        if(y + g_input[y][x] < row)
        {

            return g_dis[y + g_input[y][x]][x];
        }

        else return 0;
    }
    
}

int proc(int i, int j, int row, int col, char d[][50])
{

    int min=200,temp;
    
    temp = jump('N',i,j,row,col);

    if(temp > 0)
    {
        min = temp;

        d[i][j] = 'N';
    }
    
    temp = jump('W',i,j,row,col);

    if(temp > 0)
    {
        if(temp < min)
        {

            min = temp;
            d[i][j] = 'W';
        }
    }

    
    temp = jump('E',i,j,row,col);

    if(temp > 0)
    {
        if(temp < min)
        {

            min = temp;
            d[i][j] = 'E';
        }
    }

    
    temp = jump('S',i,j,row,col);

    if(temp > 0)
    {
        if(temp < min)
        {

            min = temp;
            d[i][j] = 'S';
        }
    }

    
    if(min != 200)return min;
    else return 0;
    
}

int proc_last(int i, int j, int row, int col, char d[][50])
{

    int min=200,temp;   
    
    temp = jump('S',i,j,row,col);

    if(temp > 0)
    {
        if(i + g_input[i][j] < row)
        {

            if(temp < g_dis[i][j] - 1)
            {
                min = temp;

                d[i][j] = 'S';
                g_dis[i][j] = temp + 1;
            }

            else if(temp == g_dis[i][j] - 1 && d[i][j] == 'X')
            {

                min = temp;
                d[i][j] = 'S';

                g_dis[i][j] = temp + 1; 
            }
        }
    }

    temp = jump('E',i,j,row,col);

    if(temp > 0)
    {
        if(j + g_input[i][j] < col)
        {

            if(g_dis[i][j + g_input[i][j]] < g_dis[i][j] - 1)
            {

                min = temp;
                d[i][j] = 'E';

                g_dis[i][j] = temp + 1;
            }
            else if(temp == g_dis[i][j]-1 && (d[i][j] == 'X' || d[i][j] == 'S'))
            {

                min = temp;
                d[i][j] = 'E';

                g_dis[i][j] = temp + 1;    
            }
        }
    }
    
    temp = jump('W',i,j,row,col);

    if(temp > 0)
    {
        if(j - g_input[i][j] >= 0)
        {

            if(g_dis[i][j - g_input[i][j]] < g_dis[i][j] - 1)
            {

                min = temp;
                d[i][j] = 'W';

                g_dis[i][j] = temp + 1;
            }
            else if(temp == g_dis[i][j]-1 && (d[i][j] == 'X' || d[i][j] == 'S' || d[i][j] == 'E'))
            {

                min = temp;
                d[i][j] = 'W';

                g_dis[i][j] = temp + 1;    
            }
        }
    }
    
    temp = jump('N',i,j,row,col);

    if(temp > 0)
    {
        if(i - g_input[i][j] >= 0)
        {

            if(g_dis[i - g_input[i][j]][j] < g_dis[i][j] - 1)
            {

                min = temp;
                d[i][j] = 'N';

                g_dis[i][j] = temp + 1;
            }
            else if(temp == g_dis[i][j] - 1 && d[i][j] != 'N')
            {

                min = temp;
                d[i][j] = 'N';

                g_dis[i][j] = temp + 1;
            }
        }
    }
 
    if(min != 200)return min;

    else return 0;
    
}

void pt(int row, int col)
{

    int i,j;
    
        for(i=0;i<row;i++)
        {

            for(j=0;j<col;j++)
            {
                cout<<ga[i][j];
            }

            cout<<endl;
        }
}

void debug_d(int row, int col)
{

    int i,j;
    for(i=0;i<row;i++)
    {

        for(j=0;j<col;j++)
        {
            cout<<g_dis[i][j]<<" ";
        }

        cout<<endl;
    }
}

int main()
{
    bool end = false;

    int row, col, i, j, temp;    
    while(1)
    {

        cin>>row>>col;
        if(0 == row || 0 == col)break;

        for(i=0; i<row; i++)
        {
            for(j=0; j<col; j++)
            {

                cin>>g_input[i][j];
            }
        }
        memset(g_dis, 0, sizeof(g_dis));

        memset(ga, 'X', sizeof(ga));
        end = false;

        ga[0][0] = '*';
        for(j=1; j<col; j++)
        {

            if(g_input[0][j] == j)
            {
                ga[0][j] = 'W';

                g_dis[0][j] = 1;
            }
        }
        for(i=1; i<row; i++)
        {

            if(g_input[i][0] == i)
            {
                ga[i][0] = 'N';

                g_dis[i][0] = 1;
            }
        }
        while(end != true)
        {

            end = true;
            for(i=0; i<row; i++)
            {

                for(j=0; j<col; j++)
                {
                    if(0 == i && 0 == j)continue;

                    if(g_dis[i][j] > 0)continue;
                    else

                    {
                        temp = proc(i,j,row,col,ga);

                        if(temp > 0)
                        {
                            g_dis[i][j] = temp+1;

                            end = false;
                        }
                    }
                }//end for j
            }//end for i
        }//while
        //last proc
        end = false;

        while(end != true)
        {
            //debug_d(row, col);
            //system("PAUSE");
            end = true;

            for(i=0; i<row; i++)
            {
                for(j=0; j<col; j++)
                {

                    if(0 == i && 0 == j)continue;

                    else
                    {
                        temp = proc_last(i,j,row,col,ga);

                        if(temp > 0)
                        {
                            //temp
                            //cout<<"ga["<<i<<"]["<<j<<"]="<<ga[i][j]<<endl;
                            //end temp*/

                            end = false;
                        }
                    }
                }//for j
            }//for i
        }//while
        //end last proc
        pt(row, col);

        cout<<endl;
    }//while(1)
    return 0;
}