naoya_t@hatenablog

いわゆるチラシノウラであります

SRM576

危うく三日坊主になるところでしたが

この回は 256-576-900 という変態的な配点です

Easy("ArcadeManao", 256)

  • プラットフォーム検出(UnionFind): 水平方向にXが隣接している時だけunionSet
  • 各プラットフォームから梯子で昇降できるプラットフォームへの距離を調べる。垂直方向への探索は最初に見つかったプラットフォームで止める。(そこから先はそのプラットフォーム経由でやればよいので)
  • 地上からダイクストラ的な何かでコインへGO!
  • AC 156.12point (26'36'')
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#define NDEBUG
// BEGIN CUT HERE
#include "cout.h"
#undef NDEBUG
// END CUT HERE
#include <cassert>

using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mid(x,y) ((x)+((y)-(x))/2)

#define cons(x,y) make_pair((x),(y))

class UnionFind {
  vector<int> data;
 public:
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};

class ArcadeManao {
 public:
  int shortestLadder(vector<string> level, int coinRow, int coinColumn) {
    int H=sz(level), W=sz(level[0]);

    --coinRow; --coinColumn;
    if (coinRow == H-1) return 0;

    UnionFind uf(H*W);
    rep(r,H) {
      rep(c,W-1) {
        if (level[r][c] != 'X') continue;
        if (level[r][c+1] == 'X') uf.unionSet(r*W+c, r*W+c+1);
      }
    }

    int goal = uf.root(coinRow*W + coinColumn);
    int start = uf.root(H*W-1);

    map<int,set<int> > adj;
    map<pair<int,int>, int> arc;

    rep(r,H-1){
      rep(c,W){
        if (level[r][c] != 'X') continue;
        int me = uf.root(r*W+c);
        for(int y=r+1; y<H; ++y) {
          if (level[y][c] != 'X') continue;
          int lo = uf.root(y*W+c);
          arc[cons(me,lo)] = arc[cons(lo,me)] = y-r;
          adj[me].insert(lo);
          adj[lo].insert(me);
          break;
        }
      }
    }

    set<int> visited;

    priority_queue<pair<int,int> > pq; // -score, root
    pq.push(cons(0, start));
    while (!pq.empty()) {
      int score = -pq.top().first, rt = pq.top().second; pq.pop();
      if (found(visited,rt)) continue;

      if (rt == goal) return score;
      visited.insert(rt);

      tr(it, adj[rt]) {
        int th = *it;
        int l = arc[cons(rt,th)];
        int sc_ = max(score, l);
        if (!found(visited, th)) {
          pq.push(cons(-sc_, th));
        }
      }
    }

    return H-1 - coinRow;
  }
};