SRM470 Div2 Hard(1000) ActivateGame

ActivateGame

貪欲にアクティブにしていけば良い。
プリム法 - Wikipedia

#include <string>
#include <vector>

using namespace std;

class ActivateGame
{
    int number( char c );
public:
    int findMaxScore( vector <string> grid );
};

int ActivateGame::findMaxScore( vector <string> grid )
{
    int N = (int)grid.size();
    int M = (int)grid[0].size();

    vector<vector<bool> > active( N, vector<bool>( M ) );
    active[0][0] = true;

    int score = 0;

    for ( int i=1; i<N*M; i++ )
    {
        int s = -1;
        int an = 0;
        int am = 0;

        for ( int n=0; n<N; n++ )
        for ( int m=0; m<M; m++ )
        if ( ! active[n][m] )
        {
            for ( int j=0; j<4; j++ )
            {
                int tn, tm;
                switch ( j )
                {
                case 0:  tn = n-1,  tm = m  ;  break;
                case 1:  tn = n+1,  tm = m  ;  break;
                case 2:  tn = n  ,  tm = m-1;  break;
                case 3:  tn = n  ,  tm = m+1;  break;
                }

                if ( 0 <= tn  &&  tn < N  &&  0 <= tm  &&  tm < M  &&
                     active[tn][tm]  &&
                     abs(number(grid[tn][tm])-number(grid[n][m])) > s )
                {
                    s = abs(number(grid[tn][tm])-number(grid[n][m]));
                    an = n,  am = m;
                }
            }
        }

        score += s;
        active[an][am] = true;
    }

    return score;
}

int ActivateGame::number( char c )
{
    if ( '0' <= c  &&  c <= '9' )  return c - '0';
    if ( 'a' <= c  &&  c <= 'z' )  return c - 'a' + 10;
    if ( 'A' <= c  &&  c <= 'Z' )  return c - 'A' + 36;
    return 0;
}