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; }