제출 #995965

#제출 시각아이디문제언어결과실행 시간메모리
995965yanbDango Maker (JOI18_dango_maker)C++14
13 / 100
1 ms604 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<long long, long long> struct Stick { int x, y; bool r; vector<pii> pos; Stick(int x, int y, bool r) { this->x = x; this->y = y; this->r = r; if (r) { pos.push_back({x, y}); pos.push_back({x, y + 1}); pos.push_back({x, y + 2}); } else { pos.push_back({x, y}); pos.push_back({x + 1, y}); pos.push_back({x + 2, y}); } } bool operator&(const Stick &s) const { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (pos[i] == s.pos[j]) return 1; } } return 0; } }; int df0, df1; void dfs(int v, int cc, vector<vector<int>> &g, vector<int> &col) { if (col[v] != -1) return; col[v] = cc; if (cc == 0) df0++; else df1++; for (int u : g[v]) { dfs(u, (cc ? 0 : 1), g, col); } } int solve(int n, vector<Stick> &a) { vector<vector<int>> g(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i] & a[j]) { g[i].push_back(j); } } } int ans = 0; vector<int> col(n, -1); for (int i = 0; i < n; i++) { df0 = df1 = 0; dfs(i, 0, g, col); ans += max(df0, df1); } return ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<char>> a(n, vector<char>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; } } vector<Stick> cand; for (int i = 0; i < n - 2; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') cand.push_back(Stick(i, j, 0)); } } for (int i = 0; i < n; i++) { for (int j = 0; j < m - 2; j++) { if (a[i][j] == 'R' && a[i][j + 1] == 'G' && a[i][j + 2] == 'W') cand.push_back(Stick(i, j, 1)); } } cout << solve(cand.size(), cand) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...