SRM467 Div2 Hard(1000) MazeOnFire - kusano

火と同じようにキャラクタを増殖させて、キャラクタが居なくなったステップを返す。キャラクタが生存していて状態が変化しなくなったら、キャラクタは死なない。

#include <string>
#include <vector>

using namespace std;

class MazeOnFire
{
    vector<string> propagate( vector<string> maze, char c );
public:
    int maximumTurns( vector <string> maze );
};

int MazeOnFire::maximumTurns( vector <string> maze )
{
    for ( int step=1; ; step++ )
    {
        vector<string> m = maze;
        m = propagate( m, '$' );
        m = propagate( m, 'F' );

        if ( m == maze )
            return -1;

        bool f = true;
        for ( int y=0; y<(int)m.size(); y++ )
        for ( int x=0; x<(int)m[y].size(); x++ )
            if ( m[y][x] == '$' )
                f = false;

        if ( f )
            return step;

        maze = m;
    }
}

vector<string> MazeOnFire::propagate( vector<string> maze, char c )
{
    int h = (int)maze.size();
    int w = (int)maze[0].size();

    vector<string> next( h, string( w, ' ' ) );

    for ( int y=0; y<h; y++ )
    for ( int x=0; x<w; x++ )
    {
        if ( ( maze[y][x] == '.'  ||
               c == 'F'  &&  maze[y][x] == '$' )  &&
             ( x >= 1   &&  maze[y][x-1] == c  ||
               y >= 1   &&  maze[y-1][x] == c  ||
               x < w-1  &&  maze[y][x+1] == c  ||
               y < h-1  &&  maze[y+1][x] == c ) )
            next[y][x] = c;
        else
            next[y][x] = maze[y][x];
    }

    return next;
}