Falling Rows
National Olympiad — Municipal round
Submission name: tetris.cpp
Problem summary
A fixed board contains occupied (*) and empty (.) cells. Its rows fall away in order without new cells appearing. Each maximal run of K consecutive completely occupied rows earns K(K+1)/2 points. Find the total score.
Input
N M followed by N strings of M board symbols.
Output
The total score.
Constraints
1 ≤ N,M ≤ 100.
Worked example
An independently prepared example for this explanation.
Input
4 2 ** ** *. **
Output
4
Solution analysis
- Scan rows while maintaining the length of the current all-occupied run.
- On a full row increase the run length and add that length to the score; otherwise reset it to zero.
Why it works
A run of K full rows contributes successive increments 1 through K, whose sum is exactly K(K+1)/2. Nonfull rows separate runs.
Complexity: O(NM) time, O(M) space.
Watch out. Do not compact columns or remove gaps before identifying runs.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: A run of K full rows contributes successive increments 1 through K, whose sum is exactly
// K(K+1)/2. Nonfull rows separate runs.
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int run=0,ans=0;
while(n--){
string s;
cin>>s;
if(s.find('.')==string::npos){
run++;
ans+=run;
}
else{
run=0;
}
}
cout<<ans<<'\n';
}