結果

問題 No.348 カゴメカゴメ
ユーザー btkbtk
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0