#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) auto write_graph() -> void; // for Graphviz constexpr int Max = 500000; // 最小の輪の敷き詰めで、輪の個数が 110889 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; int node_cost[Max]; vector tree[Max]; // to, cost 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; } count++; in[ny][nx] = nc; q.emplace(nx, ny); } } return count; } 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') { auto xcount = draw(nx, ny, 'x', RingMark); next_node_list.emplace_back(nx, ny, xcount); } } } /* rep(i, N) cout << in[i] << endl; cout << "\n\n"; */ auto const node = get<2>(nodeQP); rep(i, next_node_list.size()) { auto x = get<0>(next_node_list[i]), y = get<1>(next_node_list[i]), next_node_cost = get<2>(next_node_list[i]); tree[node].emplace_back(next_node); node_cost[next_node] = next_node_cost; rep(k, 8) { auto 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++; } } } int dp[Max][2]; auto rec(int curr, bool par_used = true) { int& ret = dp[curr][par_used]; if(ret >= 0) { return ret; } if(tree[curr].empty()) { return ret = par_used ? 0 : node_cost[curr]; } if(par_used) { ret = 0; rep(i, tree[curr].size()) { auto tar = tree[curr][i]; ret += rec(tar, false); } } else { int r1 = node_cost[curr]; rep(i, tree[curr].size()) { auto tar = tree[curr][i]; r1 += rec(tar, true); } int r2 = 0; rep(i, tree[curr].size()) { auto tar = tree[curr][i]; r2 += rec(tar, false); } ret = max(r1, r2); } return ret; } auto main() -> signed { assert(cin >> N >> M); assert(1 <= N && N <= 1000); assert(1 <= M && M <= 1000); int ncnt = 0; for(string s; cin >> s; ncnt++) { in.push_back(s); assert(in[ncnt].size() == M); } assert(ncnt == 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; vector> xposlist; rep(k, 8) { int ni = i+dy[k], nj = j+dx[k]; if(!in_range(nj, ni)) { continue; } xcount += in[ni][nj] == 'x'; if(in[ni][nj] == 'x') xposlist.emplace_back(nj, ni); } if(xcount != 2) { cout << "xcount = " << xcount << endl; rep(i, xposlist.size()) { cout << xposlist[i].first << ", " << xposlist[i].second << endl; } assert(false && "xcount is not 2."); } } } make_tree(); //write_graph(); memset(dp, -1, sizeof dp); cout << rec(0) << endl; return 0; } /* Graphviz で木の画像を生成するコマンドを打つプログラム. */ 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); }