Decode a Rotating Grille
National Olympiad — National round (2016 season)
Submission name: traf.cpp
Problem summary
Place an even-sized square grille on a text grid. Read cells marked as holes in row-major order, then rotate the grille clockwise by 90 degrees and repeat for four orientations.
Input
Even N, N grille rows using * for a hole, then N encoded text rows.
Output
The concatenated decoded message.
Constraints
2 ≤ N ≤ 100 and N is even. The given grille describes the task’s valid hole arrangement.
Worked example
Input and output for the worked example discussed below.
Input
2 *. .. ab cd
Output
abdc
Solution analysis
- Read the stationary text and the current grille into separate arrays. At an orientation, scan rows from top to bottom and columns from left to right, appending the text character exactly where the grille has *.
- Clockwise rotation maps grille cell (r,c) to (c,N−1−r). Write this into a fresh grid rather than overwriting cells that are still needed. The text itself never rotates.
- For the 2×2 example, the single hole visits top-left, top-right, bottom-right, bottom-left. Reading the fixed text ab/cd in this order gives abdc. Four orientations return the grille to its original position.
Why it works
Every orientation scan follows exactly the required reading order, and the rotation mapping produces precisely the next clockwise grille.
Watch out. Rotate the holes, not the message. Preserve row-major order after each rotation. Treat underscores as ordinary visible characters, not separators.
Commented C++17 solution
An independently written complete program with standard headers.
// Every orientation scan follows exactly the required reading order, and the rotation mapping produces
// precisely the next clockwise grille..
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
int size;
cin>>size;
vector<string>grille(size),text(size);
for(string&row:grille){
cin>>row;
}
for(string&row:text){
cin>>row;
}
string answer;
for(int turn=0;turn<4;turn++){
vector<string>rotated(size,string(size,'.'));
for(int row=0;row<size;row++){
for(int column=0;column<size;column++){
if(grille[row][column]=='*'){
answer+=text[row][column];
}
rotated[column][size-1-row]=grille[row][column];
}
}
grille=rotated;
}
cout<<answer<<'\n';
}