Domino Tiling with Fewest Cuts and Most Vertical Tiles
National Olympiad — National round (2010 season)
Submission name: tiling.cpp
Problem summary
Tile an N-by-N board except one blocked cell using whole dominoes and single-cell halves from cuts. Minimize cuts first, then maximize vertical whole dominoes.
Input
N r c with1-based blocked coordinates.
Output
Minimum cuts, maximum vertical count at minimum cuts, and horizontal count.
Constraints
2 ≤ N ≤10;1 ≤ r,c ≤N. Original full scoring requires the optimum vertical count after minimum cuts.
Worked example
Input and output for the worked example discussed below.
Input
7 3 2
Output
1 21 2
Solution analysis
- Chessboard-colour free cells. Whole dominoes are a bipartite matching between side-adjacent black and white cells. A maximum matching leaves the fewest single cells and therefore minimizes cuts.
- Assign cost0 to vertical adjacency and1 to horizontal adjacency. Build unit-capacity source→black→white→sink edges and find minimum-cost maximum flow. Bellman–Ford handles negative reverse-edge costs in each residual shortest-path search.
- For matching size F and cost H, there are F−H vertical and H horizontal tiles. Uncovered cells U=N²−1−2F need ceil(U/2) cuts. The sample has F=23,H=2,U=2, giving1 21 2. This is exact optimization, not a lower-scoring heuristic.
Why it works
Matching edges correspond exactly to nonoverlapping whole dominoes. Maximum cardinality minimizes uncovered cells and cuts. At that cardinality, minimum horizontal cost maximizes vertical count. Successive shortest residual augmentations preserve minimum cost for each flow value and terminate at maximum flow.
Watch out. Optimize cardinality before orientation. Plain Dijkstra cannot handle negative reverse costs. Cuts are ceil(uncovered/2), not the uncovered-cell count.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
struct Edge{
int to;
int reverse;
int capacity;
int cost;
};
int main(){
int n;
int blockedRow;
int blockedColumn;
cin>>n>>blockedRow>>blockedColumn;
blockedRow--;
blockedColumn--;
int source=n*n;
int sink=source+1;
int vertices=sink+1;
vector<vector<Edge>>graph(vertices);
auto addEdge=[&](int from,int to,int cost){
int forwardIndex=graph[from].size();
int reverseIndex=graph[to].size();
graph[from].push_back({to,reverseIndex,1,cost});
graph[to].push_back({from,forwardIndex,0,-cost});
};
const int dr[4]={-1,1,0,0};
const int dc[4]={0,0,-1,1};
for(int row=0;row<n;row++){
for(int column=0;column<n;column++){
if(row==blockedRow&&column==blockedColumn){
continue;
}
int vertex=row*n+column;
if((row+column)%2==0){
addEdge(source,vertex,0);
for(int direction=0;direction<4;direction++){
int r=row+dr[direction];
int c=column+dc[direction];
if(r>=0&&r<n&&c>=0&&c<n&&!(r==blockedRow&&c==blockedColumn)){
addEdge(vertex,r*n+c,row==r?1:0);
}
}
}
else{
addEdge(vertex,sink,0);
}
}
}
int flow=0;
int cost=0;
const int infinity=numeric_limits<int>::max()/4;
while(true){
vector<int>distance(vertices,infinity);
vector<int>previous(vertices,-1);
vector<int>edgeIndex(vertices,-1);
distance[source]=0;
// Bellman-Ford correctly handles negative residual reverse edges.
for(int iteration=0;iteration<vertices-1;iteration++){
bool changed=false;
for(int from=0;from<vertices;from++){
if(distance[from]==infinity){
continue;
}
for(int index=0;index<int(graph[from].size());index++){
const Edge&edge=graph[from][index];
if(edge.capacity>0&&distance[edge.to]>distance[from]+edge.cost){
distance[edge.to]=distance[from]+edge.cost;
previous[edge.to]=from;
edgeIndex[edge.to]=index;
changed=true;
}
}
}
if(!changed){
break;
}
}
if(previous[sink]==-1){
break;
}
for(int vertex=sink;vertex!=source;vertex=previous[vertex]){
Edge&edge=graph[previous[vertex]][edgeIndex[vertex]];
edge.capacity--;
graph[vertex][edge.reverse].capacity++;
}
flow++;
cost+=distance[sink];
}
int uncovered=n*n-1-2*flow;
cout<<(uncovered+1)/2<<' '<<flow-cost<<' '<<cost<<'\n';
}