結果
問題 | No.307 最近色塗る問題多くない? |
ユーザー |
|
提出日時 | 2020-01-28 19:54:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 352 ms / 4,000 ms |
コード長 | 2,403 bytes |
コンパイル時間 | 1,617 ms |
コンパイル使用メモリ | 130,824 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 16:23:10 |
合計ジャッジ時間 | 5,231 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <cstdio> #include <iostream> #include <string> #include <sstream> #include <stack> #include <algorithm> #include <cmath> #include <queue> #include <map> #include <set> #include <cstdlib> #include <bitset> #include <tuple> #include <assert.h> #include <deque> #include <bitset> #include <iomanip> #include <limits> #include <chrono> #include <random> #include <array> #include <unordered_map> #include <functional> #include <complex> template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const long long MAX = 5100000; const long long INF = 1LL << 60; const long long mod = 1000000007LL; //const long long mod = 998244353LL; using namespace std; typedef unsigned long long ull; typedef long long ll; int dh[4] = { 1,0,-1,0 }; int dw[4] = { 0,1,0,-1 }; vector<vector<int>> a; int H, W; bool bfs(ll sh, ll sw, ll x) { if (a[sh][sw] == x) return false; vector<pair<ll, ll>> vp; queue<pair<ll, ll>> q; vector<vector<bool>> used(H, vector<bool>(W, false)); q.emplace(sh, sw); vp.emplace_back(sh, sw); used[sh][sw] = true; while (!q.empty()) { ll h, w; tie(h, w) = q.front(); q.pop(); for (ll i = 0; i < 4; i++) { ll nh = h + dh[i]; ll nw = w + dw[i]; if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue; if (used[nh][nw]) continue; if (a[nh][nw] == a[h][w]) { used[nh][nw] = true; q.emplace(nh, nw); vp.emplace_back(nh, nw); } } } for (auto p : vp) { a[p.first][p.second] = x; } if (vp.size() == H * W) return true; else return false; } int main() { /* cin.tie(nullptr); ios::sync_with_stdio(false); */ scanf("%d %d", &H, &W); a = vector<vector<int>>(H, vector<int>(W)); for (ll i = 0; i < H; i++)for (ll j = 0; j < W; j++) scanf("%d", &a[i][j]); ll Q; scanf("%lld", &Q); ll last = -1; bool flag = false; while (Q--) { ll h, w, x; scanf("%lld %lld %lld", &h, &w, &x); h--; w--; if (flag) last = x; else { flag = bfs(h, w, x); last = x; } } if (flag) { for (ll i = 0; i < H; i++) { for (ll j = 0; j < W; j++) { printf("%d", last); if (j == W - 1) puts(""); else printf(" "); } } } else { for (ll i = 0; i < H; i++) { for (ll j = 0; j < W; j++) { printf("%d", a[i][j]); if (j == W - 1) puts(""); else printf(" "); } } } return 0; }