SRM453.5 Div1 Easy

250

class MazeMaker {
public:
  int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {

    const int H = maze.size();
    const int W = maze[0].size();
    const int D = moveRow.size();
    const int inf = 1 << 24;

    int cost[H][W];
    fill( &cost[0][0], &cost[H-1][W], inf );

    bool vis[H][W];
    fill( &vis[0][0], &vis[H-1][W], false );

    if( maze[startRow][startCol] == '.' ){
      cost[startRow][startCol] = 0;
      vis[startRow][startCol] = true;
    }

    queue< pair<int, int> > q;
    for( q.push( make_pair(startRow, startCol) ); q.size(); q.pop() ){
      pair<int, int> p = q.front();
      for(int d=0; d<D; ++d){
        int ni = p.first + moveRow[d];
        int nj = p.second + moveCol[d];
        if( ni < 0 || nj < 0 )continue;
        if( H <= ni || W <= nj )continue;
        if( vis[ni][nj] )continue;
        if( maze[ni][nj] == 'X' )continue;
        vis[ni][nj] = true;
        cost[ni][nj] = cost[p.first][p.second] + 1;
        q.push( make_pair(ni, nj) );
      }
    }

    int ret = 0;
    for(int i=0; i<H; ++i){
      for(int j=0; j<W; ++j){
        if( maze[i][j] == '.' )ret = max( ret, cost[i][j] );
      }
    }

    return ret == inf ? -1 : ret;
  }
};