Submission #11773027


Source Code Expand

Copy
#include <vector>
#include <queue>
using i64 = long long;

/*
 * delta(V v, fn (V t))
 * index(V v) -> int
 */
template<class V, class Delta, class Index>
std::vector<i64> bfs(std::size_t N, V s, Delta delta, Index index) {
  std::vector<i64> dist(N, -1);
  std::queue<V> que;
  dist[index(s)] = 0;
  que.push(s);
  while(!que.empty()) {
    V v = que.front();
    que.pop();
    delta(v, [&](V t) {
        if(dist[index(t)] == -1) {
          dist[index(t)] = dist[index(v)] + 1;
          que.push(t);
        }
    });
  }
  return dist;
}

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class F>
struct lattice_delta {
  i64 H, W;
  F f;
  using P = std::pair<i64, i64>;
  lattice_delta(i64 H, i64 W, F f): H(H), W(W), f(f) {}
  template<class Func>
  void operator()(P v, Func func) {
    const static vector<i64> dx { 1, 0, -1, 0 };
    i64 i = v.first;
    i64 j = v.second;
    for(i64 q = 0; q < 4; q++) {
      i64 x = i + dx[q];
      i64 y = j + dx[q ^ 1];
      if(0 <= x && x < H && 0 <= y && y < W && f(P(x, y))) {
        func(P(x, y));
      }
    }
  }
};

template<class F>
lattice_delta<F> make_lattice_delta(i64 H, i64 W, F f) { return lattice_delta<F>(H, W, f); }

struct lattice_index {
  i64 H, W;
  using P = std::pair<i64, i64>;
  lattice_index(i64 H, i64 W): H(H), W(W) {}
  i64 operator()(P v) {
    return v.first * W + v.second;
  }
};


int main() {
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  i64 H, W;
  cin >> H >> W;
  vector<string> S(H);
  rep(i,0,H) {
    cin >> S[i];
  }
  i64 ans = 0;
  using P = std::pair<i64, i64>;
  vector<i64> dx { 1, 0, -1, 0 };
  auto delta = make_lattice_delta(H, W, [&](P v) { return S[v.first][v.second] == '.'; });
  auto index = lattice_index(H, W);
  rep(i,0,H) rep(j,0,W) {
    if(S[i][j] == '#') continue;
    auto res = bfs(H * W, P(i, j), delta, index);
    ans = std::max(ans, *std::max_element(all(res)));
  }
  cout << ans << endl;
}

Submission Info

Submission Time
Task D - Maze Master
User niuez
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2134 Byte
Status
Exec Time 5 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
× 2
× 16
Set Name Test Cases
Sample sample_01, sample_02
All hand_01, hand_02, hand_03, hand_04, hand_05, hand_06, hand_07, hand_08, hand_09, hand_10, sample_01, sample_02, small_01, small_02, small_03, small_04
Case Name Status Exec Time Memory
hand_01 2 ms 256 KB
hand_02 1 ms 256 KB
hand_03 1 ms 256 KB
hand_04 2 ms 256 KB
hand_05 4 ms 256 KB
hand_06 3 ms 256 KB
hand_07 2 ms 256 KB
hand_08 5 ms 256 KB
hand_09 1 ms 256 KB
hand_10 2 ms 256 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
small_01 1 ms 256 KB
small_02 1 ms 256 KB
small_03 3 ms 256 KB
small_04 1 ms 256 KB