結果
問題 | 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_pairint 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;}