HDU : Hiking Trip


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
#define pi acos(-1.0)
#define N 1000000
using namespace std;

int cost [20 + 2] [20 + 2];
char grid [20 + 2] [20 + 2];
int R, C;
int Sr, Sc, Dr, Dc;
int Vp, Vs, Vt;
bool visited;

void reset ()
{
    for ( int i = 0; i < 22; i++ ) {
        for ( int j = 0; j < 22; j++ )
            cost [i] [j] = INT_MAX;
    }
    visited = false;
}

int calculateCost (int c, char x)
{
    if ( x == 'T' )
        return c + Vt;
    if ( x == '.' )
        return c + Vs;
    if ( x == '#' )
        return c + Vp;
    return -1;
}

void visit (int x, int y, int c)
{
    if ( visited == false ) {
        visited = true;
        visit (x - 1, y, 0);
        visit (x, y + 1, 0);
        visit (x + 1, y, 0);
        visit (x, y - 1, 0);
        return;
    }

    if ( x < 0 || x == R || y < 0 || y == C || grid [x] [y] == '@' )
        return;

    int newCost = calculateCost (c, grid [x] [y]);
    if ( newCost > cost [x] [y] )
        return;
    else
        cost [x] [y] = newCost;

    visit (x - 1, y, newCost);
    visit (x, y + 1, newCost);
    visit (x + 1, y, newCost);
    visit (x, y - 1, newCost);
}
int main ()
{
    int cases = 0;

    while ( scanf ("%d %d", &R, &C) != EOF ) {

        scanf ("%d %d %d", &Vp, &Vs, &Vt);

        reset ();

        for ( int i = 0; i < R; i++ )
            scanf ("%s", grid [i]);

        scanf ("%d %d %d %d", &Sr, &Sc, &Dr, &Dc);
        cost [Sr] [Sc] = 0;

        visit (Sr, Sc, 0);

        if ( cost [Dr] [Dc] == INT_MAX )
            printf ("Case %d: -1\n", ++cases);
        else
            printf ("Case %d: %d\n", ++cases, cost [Dr] [Dc]);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s