結果
問題 | No.348 カゴメカゴメ |
ユーザー |
![]() |
提出日時 | 2016-02-27 00:13:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,137 bytes |
コンパイル時間 | 2,042 ms |
コンパイル使用メモリ | 182,292 KB |
実行使用メモリ | 16,312 KB |
最終ジャッジ日時 | 2024-09-24 10:42:34 |
合計ジャッジ時間 | 4,664 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 WA * 9 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct node{ int sz; list<int> edge; node(){sz=1;}; }; bool check(int r,int c,int N,int M){ if(0<=r&&r<N)if(0<=c&&c<M)return true; return false; } int dir4[]={-1,0,1,0,-1}; int dir8[]={0,-1,-1,0,1,-1,1,1,0}; #define mp make_pair int main() { int N,M;cin>>N>>M;M++; vector<string> grid(N); using VB=vector<bool>; using VVB=vector<VB>; VVB used(N,VB(M,false)); vector<node> tree(1);tree[0].sz=0; auto print=[&](){ for(int i = 0; i < N; i++){ for(int j = 0; j < M; j++)cout<<grid[i][j]<<"("<<used[i][j]<<")"; cout<<endl; } }; for(auto& it : grid){ cin>>it; it="."+it; } std::function<void(int,int,int)> dfs=[&](int r,int c,int now){ used[r][c]=true; stack<pair<int,int>> W; vector<pair<int,int>> X; W.push(mp(r,c)); while(W.empty()==false){ r=W.top().first;c=W.top().second;W.pop(); // cout<<r<<c<<endl; // print(); for(int i = 0; i < 4; i++){ int nr=r+dir4[i],nc=c+dir4[i+1]; if(check(nr,nc,N,M)&&used[nr][nc]==false){ used[nr][nc]=true; if(grid[nr][nc]=='.')W.push(mp(nr,nc)); else X.push_back(mp(nr,nc)); } } } for(auto& it : X){ r=it.first,c=it.second; used[r][c]=false; } for(auto& it : X){ r=it.first,c=it.second; if(used[r][c]==false){ tree[now].edge.push_back(tree.size()); tree.push_back(node()); W.push(mp(r,c)); used[r][c]=true; while(W.empty()==false){ r=W.top().first;c=W.top().second;W.pop(); for(int i = 0; i < 8; i++){ int nr=r+dir8[i],nc=c+dir8[i+1]; if(check(nr,nc,N,M)&&used[nr][nc]==false&&grid[nr][nc]=='x'){ tree.back().sz++; used[nr][nc]=true; W.push(mp(nr,nc)); } } } for(int i = 0; i < 4; i++){ int nr=r+dir4[i],nc=c+dir4[i+1]; if(check(nr,nc,N,M)&&used[nr][nc]==false){ dfs(nr,nc,tree.size()-1); } } } } }; dfs(0,0,0); if(0)for(int i = 0; i < (int)tree.size(); i++){ printf("[%d],sz=%d,edge=",i,tree[i].sz); for(auto& it : tree[i].edge)cout<<it<<",";cout<<endl; } int Z=tree.size(); vector<pair<int,int>> dp(Z,mp(0,0)); std::function<void(int)> dfs2=[&](int v){ dp[v].first=tree[v].sz; dp[v].second=0; for(auto& u : tree[v].edge){ dfs2(u); dp[v].first+=dp[u].second; dp[v].second+=max(dp[u].first,dp[u].second); } }; dfs2(0); cout<<max(dp[0].first,dp[0].second)<<endl; return 0; }