#include #include #include using namespace std; int n, m; bool G[50][20]; int main() { cin >> n >> m; for (int i=n-1; i >= 0; i--) { string line; cin >> line; for (int j=0; j < m; j++) G[i/2][j] |= line[j] == '#'; } vector lastcans; int result = 0; for (int row = n/2 - 1; row >= 0; row--) { vector curcans1, curcans2; // delay placing cans, and if needed place to the right: for (int col = 0; col < m; col++) { // do we need to place a can here? if (G[row][col] || (find(lastcans.begin(), lastcans.end(), col-1) != lastcans.end() && (curcans1.empty() || curcans1.back() != col-2))) { curcans1.push_back(col); if (++col == m) { // move others for (int it = curcans1.size(), pos = m-1; it-- && curcans1[it] == pos; pos -= 2) curcans1[it]--; } } } // delay placing cans, and if needed place to the left: for (int col = m-1; col >= 0; col--) { // do we need to place a can here? if (G[row][col] || (find(lastcans.begin(), lastcans.end(), col) != lastcans.end() && (curcans2.empty() || curcans2.back() != col+1))) { curcans2.push_back(col-1); if (--col < 0) { // move others for (int it = curcans2.size(), pos = -1; it-- && curcans2[it] == pos; pos += 2) curcans2[it]++; } } } // now take the best option of the two: lastcans = curcans1.size() < curcans2.size() ? curcans1 : curcans2; result += lastcans.size(); } cout << result << endl; return 0; }