square869120Contest #6 C Infinite Grid

10⁹回もグリッドをつなぐ必要はなく(2H-1)回で十分ということに気づけばよかったが、そこに気づかなくても隣接行列 ( = (i, 1) から (j, w+1) に到達可能なら1, そうでなければ0) を作って累乗することでゴリ押しすることができる。

bool used[100][100];
bool mat[100][100];
bool id[100][100];

int h, w;
void bfs(int p) {
  stack<P> st;
  st.emplace(p, 0);
  while(st.size()) {
    P p = st.top(); st.pop();
    auto i = p.first;
    auto j = p.second;
    if (used[i][j]) continue;
    used[i][j] = true;
    if (i+1<h && mat[i+1][j]) {
      st.emplace(i+1, j);
    }
    if (j+1<w && mat[i][j+1]) {
      st.emplace(i, j+1);
    }
  }
}

void reset() {
  rep(i, h) rep(j, w) used[i][j] = false;
}

vector<bool> mat_mul(const vector<bool>& a, const vector<bool>& b, int n) {
  vector<bool> ret(n*n);
  rep(i, n) {
    rep(j, n) {
      rep(k, n) {
        ret[i*n+j] = a[i*n+k] && b[k*n+j];
        if (ret[i*n+j]) break;
      }
    }
  }
  return ret;
}

// return identity matrix of size n * n
vector<bool> id_mat(int n) {
  vector<bool> ret(n*n);
  rep(i, n) {
    ret[i*n+i] = true;
  }
  return ret;
}

vector<bool> mat_pow(vector<bool> a, int x, int n) {
  vector<bool> res = id_mat(n);
  while(x>0) {
    if (x&1) res = mat_mul(res, a, n);
    a = mat_mul(a, a, n); x>>=1;
  }
  return res;
}

int main() {
  cin >> h >> w;
  rep(i, h) {
    rep(j, w) {
      char c; cin >> c;
      mat[i][j] = (c == '.');
    }
  }

  vector<bool> A(h*h), B(h*h);

  rep(i, h) {
    if (mat[i][0]) {
      reset();
      bfs(i);
    }
    rep(j, h) {
      if (used[j][w-1]) {
        A[j*h+i] = true;
        if (mat[j][0]) {
          B[j*h+i] = true;
        }
      }
    }
  }

  vector<bool> BP = mat_pow(B, (1e+9)-1, h);
  vector<bool> F = mat_mul(A, BP, h);
  if (F[h*(h-1)]) {
    cout << "Yay!" << endl;
  } else {
    cout << ":(" << endl;
  }
}

提出コード: Submission #5029151 - square869120Contest #6