結果
問題 | No.697 池の数はいくつか |
ユーザー |
|
提出日時 | 2019-07-07 10:03:00 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 905 ms / 6,000 ms |
コード長 | 1,623 bytes |
コンパイル時間 | 1,645 ms |
コンパイル使用メモリ | 163,448 KB |
実行使用メモリ | 47,744 KB |
最終ジャッジ日時 | 2024-11-08 08:18:39 |
合計ジャッジ時間 | 9,573 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> lpair; const ll MOD = 1e9 + 7; const ll INF = 1e18; #define rep(i,m,n) for(ll i = (m); i < (n); i++) #define rrep(i,m,n) for(ll i = (m); i >= (n); i--) #define print(x) cout << (x) << endl; #define print2(x,y) cout << (x) << " " << (y) << endl; #define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl; bool check[3010][3010] = {}; int A[3010][3010] = {}; int main(){ cin.tie(0); ios::sync_with_stdio(false); ll H,W; cin >> H >> W; rep(i,0,H){ rep(j,0,W){ cin >> A[i][j]; } } ll ans = 0; ll dx[4] = {0,0,1,-1}; ll dy[4] = {1,-1,0,0}; rep(h,0,H){ rep(w,0,W){ if(check[h][w] == 1 || A[h][w] == 0) continue; // print2(h,w); ans++; queue<lpair> q; q.push(make_pair(h,w)); while(!q.empty()){ lpair l1 = q.front(); q.pop(); if(check[l1.first][l1.second]) continue; check[l1.first][l1.second] = 1; rep(k,0,4){ ll hy = l1.first + dy[k]; ll wx = l1.second + dx[k]; if(hy >= 0 && hy < H && wx >= 0 && wx < W){ if(check[hy][wx] == 0 && A[hy][wx] == 1){ q.push(make_pair(hy, wx)); } } } } } } print(ans); }