結果
問題 | No.307 最近色塗る問題多くない? |
ユーザー |
![]() |
提出日時 | 2015-11-28 02:11:02 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 416 ms / 4,000 ms |
コード長 | 1,952 bytes |
コンパイル時間 | 2,063 ms |
コンパイル使用メモリ | 96,272 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-21 22:00:33 |
合計ジャッジ時間 | 4,204 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <algorithm>#include <vector>#include <map>#include <set>#include <stack>#include <queue>#include <functional>#include <cmath>#ifndef ONLINE_JUDGE# include <complex># include <random># include <array># include <unordered_map># define mkt make_tuple#endif#ifdef _LOCAL# include "local/local.hpp"#else# define assert(...) ((void)0)# define ifdebug if (false)# define echo(...) ((void)0)#endifusing namespace std;typedef long long ll; typedef unsigned long long ull;#define repi(_I, _B, _E) for(int _I = (_B); (_I) < (_E); ++ (_I))#define rep(_I, _N) for(int _I = 0; (_I) < (_N); ++ (_I))#define all(_X) (_X).begin(), (_X).end()static int dx[] = { 1, 0, -1, 0 }, dy[] = { 0, 1, 0, -1 };vector<vector<bool>> board, done;int h, w;int cnt_false;void bfs(int i0, int j0, bool b){queue<pair<int, int>> que;que.push({ i0, j0 });int i, j;while ( ! que.empty() ) {tie(i, j) = que.front();que.pop();if ( 0 <= i && i < h && 0 <= j && j < w&& board[i][j] != b&& (! done[i][j])) {done[i][j] = true;board[i][j] = b;cnt_false += (b ? -1 : 1);rep(d, 4){que.push({ i + dy[d], j + dx[d] });}}}}bool completed(){return cnt_false == 0 || cnt_false == h*w;}int main(){cin >> h >> w;board.resize(h, vector<bool>(w));done.resize(h, vector<bool>(w));rep(i, h) rep(j, w){int a;cin >> a;board[i][j] = (a != 0);if ( a == 0 ) cnt_false ++;}int q;cin >> q;rep(k, q){int r, c, a;cin >> r >> c >> a;r--; c--;bool b = (a != 0);if ( completed() ) {board[0][0] = b;} else {if ( board[r][c] != b ) {bfs(r, c, b);rep(i, h) fill(all(done[i]), false);}}}rep(i, h){rep(j, w){if ( j != 0 ) cout << ' ';cout << ((completed() ? board[0][0] : board[i][j]) ? 1 : 0);}cout << endl;}return 0;}