Cinema
National Olympiad — Municipal round (2011 season)
Submission name: cinema.cpp
Problem summary
Count placements of an axis-aligned R×C rectangle containing only empty cinema seats. The rectangle cannot be rotated.
Source clarification. The narrative says the free region should have at least R rows and C columns, but the output explicitly asks for the number of R-by-C rectangles; the official example confirms fixed-size window placements.
Input
N M; R C; then N strings of M characters: . is free and # is occupied.
Output
The number of free R×C placements.
Constraints
1 ≤ R ≤ N ≤ 100; 1 ≤ C ≤ M ≤ 100.
Worked example
Official statement example.
Input
8 13 3 5 ..#...#....#. #............ ......#...... #............ ..#......#... ...#.....#... ......#...... ......#......
Output
4
Solution analysis
- Build a two-dimensional prefix sum of occupied seats. The number of occupied seats in any R×C rectangle follows from four prefix values by inclusion–exclusion.
- Enumerate its bottom-right corner over rows R through N and columns C through M. Count exactly those rectangles whose occupied count is zero. Overlapping placements are allowed.
- For the sample, the valid top-left corners are (2,2), (2,8), (2,9), and (4,5), giving four. Although the narrative says at least R and C, the output definition and example count placements of the fixed R×C window.
Why it works
Each legal top-left corner is enumerated exactly once by its bottom-right corner. Prefix inclusion–exclusion returns the exact number of occupied seats, which is zero precisely for a fully free placement. Hence the count is correct.
Watch out. Count fixed R×C placements, not all larger empty rectangles.,Do not rotate the requested dimensions.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Each legal top-left corner is enumerated exactly once by its bottom-right corner. Prefix
// inclusion–exclusion returns the exact number of occupied seats, which is zero precisely for a fully
// free placement.
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
int n,m,r,c;
cin>>n>>m>>r>>c;
vector<vector<int>>sum(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;++i){
string row;
cin>>row;
for(int j=1;j<=m;++j){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(row[j-1]=='#');
}
}
int answer=0;
for(int i=r;i<=n;++i){
for(int j=c;j<=m;++j){
int occupied=sum[i][j]-sum[i-r][j]-sum[i][j-c]+sum[i-r][j-c];
if(occupied==0){
++answer;
}
}
}
cout<<answer<<'\n';
}