Tetris Full-Row Runs
National Olympiad — Regional round (2010 season)
Submission name: tetris.cpp
Problem summary
A completed Tetris board is scored only at the end. A maximal block of k consecutive fully occupied rows earns k(k+1)/2 points. Find the total.
Input
n m, then n strings of m cells: * occupied and . empty.
Output
The total score.
Constraints
1 ≤ n,m ≤ 100.
Worked example
Input and output for the worked example discussed below.
Input
5 6 ****** ****** ****** ..*... ******
Output
7
Solution analysis
- Test each row to see whether all m cells contain *. A row with even one empty cell ends the current full-row block; no rows disappear during this scan.
- Keep run, the number of consecutive full rows ending at the current row. On a full row increment run and add run to the answer; on another row reset run to zero. A block of k rows then contributes 1+2+…+k=k(k+1)/2.
- In the sample, the first three full rows add 1,2,3. The partial fourth row resets the block, and the last row adds 1. The total is 6+1=7. This incremental formula also scores a block that reaches the last row without a special flush.
Why it works
Every maximal full-row block is scanned independently because a non-full row resets run. Its j-th row contributes j, so the contributions sum to exactly the prescribed triangular score. No incomplete row contributes.
Watch out. Do not remove rows while scanning, merge blocks across partial rows, or award only k points for a k-row block.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<string>
using namespace std;
int main(){
int n;
int m;
cin>>n>>m;
int run=0;
int score=0;
for(int row=0;row<n;row++){
string cells;
cin>>cells;
if(cells.find('.')==string::npos){
run++;
// Incremental triangular sum for the current full-row block.
score+=run;
}
else{
run=0;
}
}
cout<<score<<'\n';
}