#39900 (C++11) No.157 2つの空洞

提出ソース

結果

問題	No.157 2つの空洞
ユーザー	not_522
提出日時	2015-07-28 09:39:34
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	2 ms / 2,000 ms
コード長	6,376 bytes
コンパイル時間	2,108 ms
コンパイル使用メモリ	185,400 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-16 04:37:48
合計ジャッジ時間	2,987 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	2 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

using namespace std;

struct Edge {
  typedef int CostType;
  const static int cost = 1;
  int from, to;
  Edge(int from, int to) : from(from), to(to) {};
};

template<typename Cost> struct WeightedEdge : public Edge {
  typedef Cost CostType;
  Cost cost;
  WeightedEdge(int from, int to, Cost cost = 0) : Edge(from, to), cost(cost) {}
};

template<typename Capacity> struct ResidualEdge : public Edge {
  typedef Capacity CapacityType;
  Capacity cap;
  int rev;
  ResidualEdge(int from, int to, Capacity cap) : Edge(from, to), cap(cap) {}
  ResidualEdge reverse() const {return ResidualEdge(to, from, 0);}
};

template<typename Capacity, typename Cost> struct WeightedResidualEdge : public ResidualEdge<Capacity> {
  Cost cost;
  WeightedResidualEdge(int from, int to, Capacity cap, Cost cost) : ResidualEdge<Capacity>(from, to, cap), cost(cost) {}
  WeightedResidualEdge reverse() const {return WeightedResidualEdge(this->to, this->from, 0, -cost);}
};

template<typename Edge> class Graph {
public:
  typedef Edge EdgeType;
  virtual int size() const = 0;
  template<typename... Args> void addEdge(Args...) {}
  template<typename... Args> void addUndirectedEdge(Args...) {}
  virtual vector<Edge> getEdges() const = 0;
  virtual vector<Edge> getEdges(int from) const = 0;
  virtual vector<Edge> getEdges(int from, int to) const = 0;
  virtual int getDegree(int v) const = 0;
};

template<typename Edge> class AdjacencyList : public Graph<Edge> {
protected:
  vector<vector<Edge>> graph;

public:
  AdjacencyList(int n) : graph(n) {}

  int size() const {
    return graph.size();
  }
  
  template<typename... Args> void addEdge(Args... args) {
    Edge edge(args...);
    graph[edge.from].emplace_back(edge);
  }

  template<typename... Args> void addUndirectedEdge(Args... args) {
    Edge edge(args...);
    addEdge(edge);
    swap(edge.from, edge.to);
    addEdge(edge);
  }

  vector<Edge> getEdges() const {
    vector<Edge> res;
    for (const auto& edges : graph) {
      res.insert(res.end(), edges.begin(), edges.end());
    }
    return res;
  }

  vector<Edge> getEdges(int from) const {
    return graph[from];
  }

  vector<Edge> getEdges(int from, int to) const {
    vector<Edge> res;
    for (const auto& edge : graph[from]) {
      if (edge.to == to) res.emplace_back(edge);
    }
    return res;
  }

  int getDegree(int v) const {
    return graph[v].size();
  }

  vector<Edge>& operator[](int v) {
    return graph[v];
  }
};

template<typename Graph, typename State> class Search {
protected:
  typedef typename Graph::EdgeType Edge;

  const Graph graph;
  vector<bool> visited;

  virtual void push(const State&) = 0;
  virtual State next() = 0;
  virtual bool isRunning() = 0;

  virtual void visit(const State&) {}
  virtual bool canPruning(const State&) {return false;}

public:
  Search(const Graph& graph) : graph(graph), visited(graph.size(), false) {}

  void solve(int from) {
    push(State(from));
    while (isRunning()) {
      State now = next();
      int pos = now.getPos();
      if (visited[pos]) continue;
      visited[pos] = true;
      visit(now);
      for (const Edge& edge : graph.getEdges(pos)) {
        State nextState = now.next(edge);
        if (visited[nextState.getPos()]) continue;
        if (canPruning(nextState)) continue;
        push(nextState);
      }
    }
  }

  bool isReachable(int v) {
    return visited[v];
  }
};

template<typename Edge> struct WeightedBFSState {
  typedef typename Edge::CostType Cost;

  Edge edge;
  Cost cost;

  WeightedBFSState(int pos, int prv = -1) : edge(prv, pos), cost(0) {}

  WeightedBFSState(const Edge& edge, Cost cost) : edge(edge), cost(cost) {}

  WeightedBFSState next(const Edge& edge) const {
    return WeightedBFSState(edge, cost + edge.cost);
  }

  int getPos() {
    return edge.to;
  }
};

template<typename Graph, typename State = WeightedBFSState<typename Graph::EdgeType>> class WeightedBFS : public Search<Graph, State> {
protected:
  typedef typename Graph::EdgeType Edge;
  typedef typename Edge::CostType Cost;

private:
  Cost now;
  deque<queue<State>> que;
  
  void push(const State& state) {
    if (state.cost - now >= que.size()) que.resize(state.cost - now + 1);
    que[state.cost - now].push(state);
  }
  
  State next() {
    State now = que[0].front();
    que[0].pop();
    return now;
  }
  
  bool isRunning() {
    while (!que.empty() && que[0].empty()) {
      que.pop_front();
      ++now;
    }
    return !que.empty();
  }

public:
  WeightedBFS(const Graph& graph) : Search<Graph, State>(graph), now(0) {}
};

namespace weighted_bfs_distance {
  template<typename Graph> class WeightedBFSDistance : public WeightedBFS<Graph> {
  private:
    typedef WeightedBFSState<typename Graph::EdgeType> State;

    void visit(const State& state) {
      if (state.edge.from != -1) dis[state.edge.to] = dis[state.edge.from] + state.edge.cost;
    }

  public:
    vector<int> dis;

    WeightedBFSDistance(const Graph& graph) : WeightedBFS<Graph>(graph), dis(graph.size(), 0) {}
  };
}

template<typename Graph> inline weighted_bfs_distance::WeightedBFSDistance<Graph> weightedBFSDistance(const Graph& graph, int from) {
  weighted_bfs_distance::WeightedBFSDistance<Graph> bfs(graph);
  bfs.solve(from);
  return bfs;
}

int main() {
  int w, h;
  cin >> w >> h;
  vector<string> c(h);
  for (auto& i : c) cin >> i;
  AdjacencyList<WeightedEdge<int>> graph(w * h);
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w - 1; ++j) {
      graph.addEdge(i * w + j, i * w + j + 1, c[i][j + 1] == '.' ? 0 : 1);
    }
    for (int j = 0; j < w - 1; ++j) {
      graph.addEdge(i * w + j + 1, i * w + j, c[i][j] == '.' ? 0 : 1);
    }
  }
  for (int i = 0; i < h - 1; ++i) {
    for (int j = 0; j < w; ++j) {
      graph.addEdge(i * w + j, i * w + j + w, c[i + 1][j] == '.' ? 0 : 1);
    }
    for (int j = 0; j < w; ++j) {
      graph.addEdge(i * w + j + w, i * w + j, c[i][j] == '.' ? 0 : 1);
    }
  }
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (c[i][j] == '.') {
        auto dis = weightedBFSDistance(graph, i * w + j).dis;
        int res = 0;
        for (int a = 0; a < h; ++a) {
          for (int b = 0; b < w; ++b) {
            if (c[a][b] == '.') res = max(res, dis[a * w + b]);
          }
        }
        cout << res << endl;
        return 0;
      }
    }
  }
}

yukicoder

結果

テストケース

ソースコード