Submission #3725099
Source Code Expand
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
bool hori(int di, int dj) { return abs(di) == 0 and abs(dj) == 1; }
bool vert(int di, int dj) { return abs(di) == 1 and abs(dj) == 0; }
bool diag(int di, int dj) { return abs(di) == 1 and abs(dj) == 1; }
bool can(int di, int dj) { return hori(di, dj) or vert(di, dj); }
template <typename signature> using f = const function<signature>&;
void flood(vector<vector<bool>>& a, f<bool(int, int)> can, f<void(int, int, int, int)> f) {
int n = a.size() - 2, m = a[0].size() - 2;
vector<vector<bool>> vis(n + 2, vector<bool>(m + 2));
function<void(int, int, int, int)> dfs = [&](int i, int j, int from_i, int from_j) {
if(a[i][j] and not vis[i][j]) {
f(i, j, from_i, from_j);
vis[i][j] = true;
for(int di = -1; di <= 1; di++) {
for(int dj = -1; dj <= 1; dj++) {
if(can(di, dj)) {
dfs(i + di, j + dj, i, j);
}
}
}
}
};
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(not vis[i][j]) {
dfs(i, j, 0, 0);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
const int n = 10;
vector<vector<bool>> a(n + 2, vector<bool>(n + 2));
for(int i = 1; i <= n; i++) {
string s;
cin >> s;
for(int j = 1; j <= n; j++) {
a[i][j] = s[j - 1] == 'o';
}
}
vector<vector<int>> component(n + 2, vector<int>(n + 2));
int id = 0;
flood(a, can, [&](int i, int j, int from_i, int from_j) {
component[i][j] = from_i ? component[from_i][from_j] : ++id;
});
bool can = id == 1;
for(int i = 1; i <= n and not can; i++) {
for(int j = 1; j <= n and not can; j++) {
if(not a[i][j]) {
set<int> neighbors;
for(int di = -1; di <= 1; di++) {
for(int dj = -1; dj <= 1; dj++) {
if((hori(di, dj) or vert(di, dj)) and a[i + di][j + dj]) {
neighbors.insert(component[i + di][j + dj]);
}
}
}
can |= neighbors.size() == id;
}
}
}
cout << (can ? "YES" : "NO") << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
B - 埋め立て |
User |
verngutz |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2534 Byte |
Status |
AC |
Exec Time |
2 ms |
Memory |
384 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt |
All |
00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 10_rand_00.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 10_rand_09.txt, 10_rand_10.txt, 10_rand_11.txt, 10_rand_12.txt, 10_rand_13.txt, 10_rand_14.txt, 10_rand_15.txt, 10_rand_16.txt, 10_rand_17.txt, 10_rand_18.txt, 10_rand_19.txt, 10_rand_20.txt, 10_rand_21.txt, 10_rand_22.txt, 10_rand_23.txt, 10_rand_24.txt, 10_rand_25.txt, 10_rand_26.txt, 10_rand_27.txt, 10_rand_28.txt, 10_rand_29.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample_00.txt |
AC |
1 ms |
256 KB |
00_sample_01.txt |
AC |
1 ms |
256 KB |
00_sample_02.txt |
AC |
1 ms |
256 KB |
10_rand_00.txt |
AC |
1 ms |
256 KB |
10_rand_01.txt |
AC |
1 ms |
256 KB |
10_rand_02.txt |
AC |
2 ms |
384 KB |
10_rand_03.txt |
AC |
1 ms |
256 KB |
10_rand_04.txt |
AC |
1 ms |
256 KB |
10_rand_05.txt |
AC |
1 ms |
256 KB |
10_rand_06.txt |
AC |
1 ms |
256 KB |
10_rand_07.txt |
AC |
1 ms |
256 KB |
10_rand_08.txt |
AC |
1 ms |
256 KB |
10_rand_09.txt |
AC |
1 ms |
256 KB |
10_rand_10.txt |
AC |
1 ms |
256 KB |
10_rand_11.txt |
AC |
1 ms |
256 KB |
10_rand_12.txt |
AC |
1 ms |
256 KB |
10_rand_13.txt |
AC |
1 ms |
256 KB |
10_rand_14.txt |
AC |
1 ms |
256 KB |
10_rand_15.txt |
AC |
1 ms |
256 KB |
10_rand_16.txt |
AC |
1 ms |
256 KB |
10_rand_17.txt |
AC |
1 ms |
256 KB |
10_rand_18.txt |
AC |
1 ms |
256 KB |
10_rand_19.txt |
AC |
1 ms |
256 KB |
10_rand_20.txt |
AC |
1 ms |
256 KB |
10_rand_21.txt |
AC |
1 ms |
256 KB |
10_rand_22.txt |
AC |
1 ms |
256 KB |
10_rand_23.txt |
AC |
1 ms |
256 KB |
10_rand_24.txt |
AC |
1 ms |
256 KB |
10_rand_25.txt |
AC |
1 ms |
256 KB |
10_rand_26.txt |
AC |
1 ms |
256 KB |
10_rand_27.txt |
AC |
1 ms |
256 KB |
10_rand_28.txt |
AC |
1 ms |
256 KB |
10_rand_29.txt |
AC |
1 ms |
256 KB |