Validate a Tromino Covering
National Olympiad — National round (2018 season)
Submission name: trimino.cpp
Problem summary
A grid uses zero for uncovered cells and a positive label for each placed piece. Decide whether every present label occupies exactly three side-connected cells and at most two cells are uncovered.
Input
T cases, each M N and M×N labels.
Output
YES or NO for each case.
Constraints
2 ≤ T ≤ 10; 1 ≤ M,N ≤ 200; 0 ≤ label ≤ floor(MN/3).
Worked example
Input and output for the worked example discussed below.
Input
2 2 3 1 1 1 2 2 2 2 3 1 0 1 0 0 1
Output
YES NO
Solution analysis
- Group cell coordinates by their positive labels and count zero cells. Every used label must occur exactly three times. Unused labels are harmless.
- For the three cells of one label, count the unordered side-adjacent pairs: Manhattan distance 1 means a shared side. Exactly three cells form a connected tromino precisely when at least two such pairs exist.
- The first sample has two horizontal three-cell pieces and no holes, so is valid. The second has three uncovered cells, already exceeding the allowed two. Disconnected equal labels must also be rejected even if their total count is three.
Why it works
Three grid cells form a connected figure exactly when their adjacency graph is connected; on three vertices this is equivalent to having at least two side-adjacency edges.
Watch out. Count all cells sharing one label as one piece. Diagonal contact does not connect a tromino. Reject four occurrences of one label rather than splitting them.
Commented C++17 solution
An independently written complete program with standard headers.
// Three grid cells form a connected figure exactly when their adjacency graph is connected; on three vertices
// this is equivalent to having at least two side-adjacency edges..
#include<cstdlib>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
int tests;
cin>>tests;
while(tests--){
int rows,columns;
cin>>rows>>columns;
vector<vector<pair<int,int>>>cells(rows*columns/3+1);
int empty=0;
for(int row=0;row<rows;row++){
for(int column=0;column<columns;column++){
int label;
cin>>label;
if(label==0){
empty++;
}
else{
cells[label].push_back({row,column});
}
}
}
bool valid=empty<=2;
for(const auto&piece:cells){
if(piece.empty()){
continue;
}
if(piece.size()!=3){
valid=false;
continue;
}
int edges=0;
for(int first=0;first<3;first++){
for(int second=first+1;second<3;second++){
edges+=abs(piece[first].first-piece[second].first)+
abs(piece[first].second-piece[second].second)==
1;
}
}
valid=valid&&edges>=2;
}
cout<<(valid?"YES":"NO")<<'\n';
}
}