제출 #521883

#제출 시각아이디문제언어결과실행 시간메모리
521883MonarchuwuDango Maker (JOI18_dango_maker)C++17
13 / 100
141 ms212216 KiB
#include<iostream> #include<algorithm> #include<vector> #include<queue> using namespace std; typedef long long ll; const int N = 3000 + 3, N2 = N * N, inf = 1e9 + 7; int m, n; char c[N][N]; int cntX, cntY; int num[N][N]; vector<int> g[N2]; void init_graph() { int cnt(0); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (c[i][j] == 'R') { if (j + 2 < n && c[i][j + 1] == 'G' && c[i][j + 2] == 'W') num[i][j] = ++cnt; else if (i + 2 < m && c[i + 1][j] == 'G' && c[i + 2][j] == 'W') num[i][j] = ++cnt; } cntX = cnt; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (c[i][j] == 'W') { if (j >= 2 && c[i][j - 1] == 'G' && c[i][j - 2] == 'R') { num[i][j] = ++cnt; g[num[i][j - 2]].push_back(cnt); } else if (i >= 2 && c[i - 1][j] == 'G' && c[i - 2][j] == 'R') { num[i][j] = ++cnt; g[num[i - 2][j]].push_back(cnt); } } cntY = cnt; } int mat[N2]; int dist[N2]; bool bfs() { queue<int> q; dist[0] = inf; for (int i = 1; i <= cntX; ++i) if (mat[i]) dist[i] = inf; else { dist[i] = 0; q.push(i); } while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (dist[mat[v]] == inf) { dist[mat[v]] = dist[u] + 1; q.push(mat[v]); } } } return dist[0] != inf; } bool dfs(int u) { for (int v : g[u]) { if (!mat[v] || dfs(mat[v])) { mat[v] = u, mat[u] = v; dist[u] = inf; return true; } } dist[u] = inf; return false; } int hopcroft_karp() { int ans(0); while (bfs()) { for (int i = 1; i <= cntX; ++i) if (!mat[i] && dfs(i)) ++ans; } return ans; } int main() { cin.tie(NULL)->sync_with_stdio(false); cin >> m >> n; for (int i = 0; i < m; ++i) cin >> c[i]; init_graph(); cout << hopcroft_karp() << '\n'; } /** /\_/\ * (= ._.) * / >0 \>1 **/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...