cafelier@SRM

SRM515 1000

あとで | 21:03 |

Rからの距離をBFSしてFからの距離をBFSして足し算してそこからLまでの距離をBFS。

static const int INF = 0x3fffffff;
LL gcd(LL x, LL y) { while(x) swap(x,y%=x); return y; }
static const int dy[] = {-1,+1,0,0};
static const int dx[] = {0,0,-1,+1};

class MeetInTheMaze { public:
   int H, W;
   map<char, int> count;

   void setup_maze(vector<string>& maze)
   {
      setup_sentinel(maze);

      H = maze.size();
      W = maze[0].size();

      for(int y=0; y<H; ++y)
      for(int x=0; x<W; ++x)
         count[maze[y][x]] ++;
   }

   void setup_sentinel(vector<string>& maze)
   {
      for(int y=0; y<maze.size(); ++y)
         maze[y] = '#' + maze[y] + '#';
      maze.insert( maze.begin(), string(maze[0].size(), '#') );
      maze.insert( maze.end(),   string(maze[0].size(), '#') );
   }

   string ratio2str(LL si, LL bo)
   {
      if( si >= INF )
         return "";
      LL g = gcd(si, bo);
      stringstream ss;
      ss << si/g << "/" << bo/g;
      return ss.str();
   }

   LL dijkstra(const vector< vector<int> >& FD, const vector< vector<int> >& RD, const vector<string>& maze)
   {
      typedef pair<int,int>   vert;
      typedef LL              cost;
      typedef pair<cost,vert> cvert;

      vector<bool> V(H*W);
      priority_queue< cvert, vector<cvert>, greater<cvert> > Q;
      for(int y=0; y<H; ++y)
      for(int x=0; x<W; ++x)
         if( maze[y][x] != '#' )
            Q.push( cvert(FD[y][x]+RD[y][x], make_pair(y,x)) );

      cost total = 0;
      while( !Q.empty() )
      {
         cvert v = Q.top(); Q.pop();
         cost c = v.first;
         int y = v.second.first;
         int x = v.second.second;
         if( V[y*W+x] )
            continue;
         V[y*W+x] = true;

         if( maze[y][x] == 'L' )
            total += c;

         for(int k=0; k<4; ++k) {
            int yy = y+dy[k];
            int xx = x+dx[k];
            cvert u(c+1, make_pair(yy,xx));
            if( maze[yy][xx]!='#' && !V[yy*W+xx] )
               Q.push(u);
         }
      }
      return total;
   }

   void bfs(vector< vector<int> >& D, vector<string>& m, int y, int x)
   {
      vector< pair<int,int> > Q(1, make_pair(y,x));
      D[y][x] = 0;
      for(int s=1; !Q.empty(); ++s)
      {
         vector< pair<int,int> > Q2;
         for(int i=0; i<Q.size(); ++i){
            y = Q[i].first;
            x = Q[i].second;
            for(int k=0; k<4; ++k) {
               int yy = y+dy[k];
               int xx = x+dx[k];
               if( m[yy][xx]!='#' && D[yy][xx]==INF )
                  Q2.push_back(make_pair(yy,xx)), D[yy][xx]=s;
            }
         }
         Q.swap(Q2);
      }
   }

   string getExpected(vector <string> maze)
   {
      setup_maze(maze);

      LL total = 0;
      for(int fy=0; fy<H; ++fy)
      for(int fx=0; fx<W; ++fx)
      if( maze[fy][fx] == 'F' )
      {
         // Fill the 2d-map FD with the distance from (fy,fx) in the maze.
         vector< vector<int> > FD(H, vector<int>(W, INF));
         bfs(FD, maze, fy, fx);
         for(int ry=0; ry<H; ++ry)
         for(int rx=0; rx<W; ++rx)
         if( maze[ry][rx] == 'R' )
         {
            // Fill the 2d-map RD with the distance from (ry,rx) in the maze.
            vector< vector<int> > RD(H, vector<int>(W, INF));
            bfs(RD, maze, ry, rx);
            // Compute the distances of all the cells from the base "FD+RD"
            total += dijkstra(FD, RD, maze);
         }
      }
      return ratio2str(total, count['F']*count['R']*count['L']);
   }
};

最後のBFSは距離の違う始点がたくさんあるので手抜きでDijkstraにした。やってることの単純さに比べて綺麗に書けないなあ。むむむ。