#include #include #include #include using namespace std; int main() { int r, c, s, t; cin >> r >> c >> s >> t; vector g(r); for(auto& x: g) cin >> x; vector heights(c); vector> rdp(r); vector> cdp(c); for(auto& x: rdp) x.resize(c+1); for(auto& x: cdp) x.resize(r+1); for(int i = 0; i < r; i++) { for(int j = 0; j < c; j++) { rdp[i][j+1] = rdp[i][j] + (g[i][j] == '0'); cdp[j][i+1] = cdp[j][i] + (g[i][j] == '0'); } } int ret = 0; for(int i = 0; i < r; i++) { cerr << endl; cerr << "looping over row " << i << endl; for(int j = 0; j < c; j++) { if(g[i][j] == '0') heights[j] = 0; else heights[j]++; } vector> st; for(int j = 0; j < c; j++) { int clhs = j; while(st.size() && st.back()[0] > heights[j]) { array curr = st.back(); st.pop_back(); int lhs = curr[1]; clhs = lhs; int width = (j - lhs); int height = curr[0]; if(width >= s && height >= t); else if(width >= t && height >= s); else continue; // make sure cannot extend above if(i+1 == r || rdp[i+1][j] - rdp[i+1][lhs]); else continue; // make sure cannot extend left if(st.size() == 0 || st.back()[0] < curr[0]); else { assert(st.back()[0] == curr[0]); continue; } bool valid = true; ret += valid; } st.push_back({heights[j], clhs}); } while(st.size()) { array curr = st.back(); st.pop_back(); int lhs = curr[1]; int width = c - lhs; int height = curr[0]; if(width >= s && height >= t); else if(width >= t && height >= s); else continue; if(i+1 == r || rdp[i+1][c] - rdp[i+1][lhs]); else continue; if(st.size() == 0 || st.back()[0] < curr[0]); else { assert(st.back()[0] == curr[0]); continue; } ret++; } } cout << ret << "\n"; }