제출 #234273

#제출 시각아이디문제언어결과실행 시간메모리
234273jungsnowZoo (COCI19_zoo)C++14
45 / 110
2088 ms10072 KiB
#include<bits/stdc++.h> #define fi first #define se second using namespace std; typedef pair<int, int> ii; const int N = 1015; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, 1, -1}; char C[N][N]; int n, m; bool vist[N][N]; inline bool check(int r, int c) { return (r > 0 && r <= n && c > 0 && c <= m && C[r][c] == C[1][1] && !vist[r][c]); } inline char other(char c) { if (c == 'T') return 'B'; return 'T'; } int flood_fill() { vector< ii > v; queue< ii > q; q.push({1, 1}); vist[1][1] = 1; while (q.size()) { ii cur = q.front(); q.pop(); v.push_back(cur); for (int i = 0; i < 4; i++) { int u = cur.fi + dx[i]; int v = cur.se + dy[i]; if (check(u, v)) { q.push({u, v}); vist[u][v] = 1; } } } char c = other(C[1][1]); for (auto &p : v) { C[p.fi][p.se] = c; vist[p.fi][p.se] = 0; } return v.size(); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; int cn = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> C[i][j]; cn += (C[i][j] != '*'); } } int sol = 1; while (flood_fill() < cn) ++sol; cout << sol; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...