結果
問題 | No.307 最近色塗る問題多くない? |
ユーザー | jupiro |
提出日時 | 2020-01-28 19:54:42 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 6 ms
5,376 KB |
testcase_08 | AC | 31 ms
5,376 KB |
testcase_09 | AC | 12 ms
5,376 KB |
testcase_10 | AC | 11 ms
5,376 KB |
testcase_11 | AC | 21 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 11 ms
5,376 KB |
testcase_14 | AC | 3 ms
5,376 KB |
testcase_15 | AC | 4 ms
5,376 KB |
testcase_16 | AC | 3 ms
5,376 KB |
testcase_17 | AC | 19 ms
5,376 KB |
testcase_18 | AC | 56 ms
5,376 KB |
testcase_19 | AC | 50 ms
5,376 KB |
testcase_20 | AC | 3 ms
5,376 KB |
testcase_21 | AC | 37 ms
5,376 KB |
testcase_22 | AC | 34 ms
5,376 KB |
testcase_23 | AC | 317 ms
5,376 KB |
testcase_24 | AC | 98 ms
5,376 KB |
testcase_25 | AC | 161 ms
5,376 KB |
testcase_26 | AC | 352 ms
5,376 KB |
testcase_27 | AC | 301 ms
5,376 KB |
testcase_28 | AC | 174 ms
5,376 KB |
testcase_29 | AC | 8 ms
5,376 KB |
testcase_30 | AC | 344 ms
5,376 KB |
testcase_31 | AC | 304 ms
5,376 KB |
testcase_32 | AC | 19 ms
5,376 KB |
testcase_33 | AC | 13 ms
5,376 KB |
testcase_34 | AC | 19 ms
5,376 KB |
testcase_35 | AC | 21 ms
5,376 KB |
ソースコード
#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; }