#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) typedef long long ll; auto write_graph() -> void; constexpr int Max = 1000*1000+1; constexpr int dx[] = {-1,0,1,0,-1,1,1,-1}; constexpr int dy[] = {0,-1,0,1,-1,-1,1,1}; constexpr char VisMark = ' '; constexpr char RingMark = 'o'; int N, M; vector in; vector tree[Max]; constexpr auto in_range(int x, int y) { return 0<=x&&x> q; q.emplace(x, y); while(!q.empty()) { auto p = q.front(); q.pop(); int x = p.first, y = p.second; rep(i, 8) { int nx = x+dx[i], ny = y+dy[i]; if(!in_range(nx, ny)) { continue; } if(in[ny][nx] != c) { continue; } in[ny][nx] = nc; q.emplace(nx, ny); } } } auto find_outer_land() { rep(i, N) { if(in[i][0] == '.') return make_pair(0, i); if(in[i][M-1] == '.') return make_pair(M-1, i); } rep(i, M) { if(in[0][i] == '.') return make_pair(i, 0); if(in[N-1][i] == '.') return make_pair(i, N-1); } assert(false); } auto make_tree() { queue> nodeQ; // 外側の . をみつける auto outer_land = find_outer_land(); int next_node = 0; nodeQ.emplace(outer_land.first, outer_land.second, next_node++); // BFS木を作るBFS while(!nodeQ.empty()) { auto const nodeQP = nodeQ.front(); nodeQ.pop(); queue> q; q.emplace(get<0>(nodeQP), get<1>(nodeQP)); in[get<1>(nodeQP)][get<0>(nodeQP)] = VisMark; vector> next_node_list; // 次の深さの輪を見つけるために、同じ深さの'.'を訪れるBFS while(!q.empty()) { auto const p = q.front(); q.pop(); auto const x = get<0>(p), y = get<1>(p); rep(i, 8) { auto const nx = x+dx[i], ny = y+dy[i]; if(!in_range(nx, ny)) { continue; } // '.' は訪れるだけ if(in[ny][nx] == '.') { if(i > 3 && in[y+dy[i-4]][x+dx[i-4]] != '.' && in[y+dy[(i-3)%4]][x+dx[(i-3)%4]] != '.') { continue; } in[ny][nx] = VisMark; q.emplace(nx, ny); } // 'x' は輪の要素なので、一つ見つけてあとは塗りつぶす if(in[ny][nx] == 'x') { draw(nx, ny, 'x', RingMark); next_node_list.emplace_back(nx, ny); } } } /* rep(i, N) cout << in[i] << endl; cout << "\n\n"; */ auto const node = get<2>(nodeQP); rep(i, next_node_list.size()) { tree[node].push_back(next_node); // add_edge(node, next_node); int x = next_node_list[i].first, y = next_node_list[i].second; rep(k, 8) { int nx = x+dx[k], ny = y+dy[k]; if(!in_range(nx, ny)) { continue; } if(in[ny][nx] == '.') { nodeQ.emplace(nx, ny, next_node); break; } } next_node++; } } } ll dp[1000*1000+1][2]; auto rec(int curr, bool par_used = true) { ll& ret = dp[curr][par_used]; if(ret >= 0) { return ret; } if(tree[curr].empty()) { return ret = par_used ? 0 : 1; } if(par_used) { ret = 0; rep(i, tree[curr].size()) { int tar = tree[curr][i]; ret += rec(tar, false); } } else { int r1 = 1; rep(i, tree[curr].size()) { int tar = tree[curr][i]; r1 += rec(tar, true); } int r2 = 0; rep(i, tree[curr].size()) { int tar = tree[curr][i]; r2 += rec(tar, false); } ret = max(r1, r2); } return ret; } auto main() -> int { cin >> N >> M; rep(i, N) { string s; cin >> s; in.push_back(s); assert(in[i].size() == M); } assert(in.size() == N); rep(i, N) rep(j, M) assert(in[i][j] == '.' || in[i][j] == 'x'); rep(i, N) { rep(j, M) { if(in[i][j] != 'x') { continue; } int xcount = 0; rep(k, 8) { int ni = i+dy[k], nj = j+dx[k]; if(!in_range(nj, ni)) { continue; } xcount += in[ni][nj] == 'x'; } assert(xcount == 2); } } make_tree(); // write_graph(); memset(dp, -1, sizeof dp); cout << rec(0) << endl; return 0; } auto write_graph() -> void { ofstream ofs("tree.dot"); ofs << "digraph G {\n"; rep(i, Max) { for(auto const& tar: tree[i]) { ofs << " " << i << " -> " << tar << ";\n"; } } ofs << "}\n"; ofs.close(); int ret, state; ret = system("dot -Tpng tree.dot > tree.png"); if(WIFEXITED(ret)){ state = WEXITSTATUS(ret); } else{ state = -1; } printf("STATUS = %d\n", state); // exit(ret); }