Catching an Invisible Knight
Autumn Tournament (2018)
Submission name: chess.cpp
Problem summary
An invisible knight starts on any accessible board square. Between consecutive shots it may make zero or one legal knight move, and in total at most K moves. A shot destroys it only if it currently occupies that square; squares remain accessible. Output a shortest guaranteed sequence of shots.
Source clarification. The official editorial explains matching and cover sweeps. This implementation explicitly separates isolated squares, which cannot move and need only one shot.
Input
N M K, then N rows of M characters: . accessible, # blocked. Coordinates start at (0,0).
Output
The minimum number of shots, then that many row/column pairs in firing order. Any optimal sequence is accepted.
Constraints
1 ≤ N,M,K ≤ 100.
Worked example
An independently prepared valid example; output follows the implementation below.
Input
1 1 3 .
Output
1 0 0
Solution analysis
- Make a graph whose vertices are accessible squares and whose edges are knight moves. A knight changes the parity of row+column, so this graph is bipartite. Isolated vertices require exactly one shot because a knight there cannot escape. Handle them separately, especially when K>1.
- For each remaining vertex, t=floor(K/2)+1 shots are necessary: with a neighbor, a knight can evade each of its first t−1 shots by leaving just before it and returning afterward, spending two moves each time. If K is odd, the vertices receiving an additional shot must cover every edge. Otherwise the knight can alternate along an uncovered edge to evade the two endpoints. Thus choose a minimum vertex cover C and let I be its independent complement.
- Find a maximum matching with Hopcroft–Karp. Starting at unmatched left vertices, follow unmatched edges left-to-right and matched edges right-to-left. König’s theorem gives a minimum cover: unreached left vertices together with reached right vertices. Print C,I alternately t times; if K is odd, print C once more. The independent set has no internal edges, so surviving an entire sweep forces movement between the two sets.
- Worked example: a board containing only one accessible square has no knight edges. Even with K=3, shoot (0,0) once. For two accessible squares joined by a knight move, the minimum cover has size one. K=1 gives three shots C,I,C; K=2 gives four shots C,I,C,I. This illustrates why isolated squares must not be blindly repeated.
Why it works
The per-vertex evasion argument gives t shots per nonisolated square. For odd K, the extra-shot set must be a vertex cover, so at least |C| additional shots are necessary. The alternating cover/complement sweeps meet these lower bounds: since I is independent, any surviving knight must cross the cover boundary enough times to exceed its move budget. Isolated squares require and receive one shot. Maximum matching and alternating reachability produce a minimum cover in this bipartite graph.
Watch out. Use board coordinates starting at zero, not graph-index coordinates. A knight may stay still between shots. Do not treat a shot as blocking a square. Isolated vertices need one shot only. Keep the repeated cover/independent order; merely printing the right multiplicities in an arbitrary order is insufficient.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<functional>
#include<iostream>
#include<queue>
#include<string>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int rows,columns,moves;
cin>>rows>>columns>>moves;
vector<string>board(rows);
for(string&row:board){
cin>>row;
}
vector<pair<int,int>>cell;
vector<vector<int>>id(rows,vector<int>(columns,-1));
for(int r=0;r<rows;++r){
for(int c=0;c<columns;++c){
if(board[r][c]=='.'){
id[r][c]=static_cast<int>(cell.size());
cell.emplace_back(r,c);
}
}
}
int n=static_cast<int>(cell.size());
vector<vector<int>>graph(n);
vector<int>left;
const int dr[]={-2,-2,-1,-1,1,1,2,2};
const int dc[]={-1,1,-2,2,-2,2,-1,1};
for(int u=0;u<n;++u){
auto[r,c]=cell[u];
if((r+c)%2==0){
left.push_back(u);
}
for(int d=0;d<8;++d){
int nr=r+dr[d];
int nc=c+dc[d];
if(nr>=0&&nr<rows&&nc>=0&&nc<columns&&id[nr][nc]!=-1){
graph[u].push_back(id[nr][nc]);
}
}
}
vector<int>mate(n,-1),distance(n);
// Hopcroft-Karp: augment along a whole layer of shortest alternating paths.
while(true){
fill(distance.begin(),distance.end(),-1);
queue<int>pending;
for(int u:left){
if(mate[u]==-1){
distance[u]=0;
pending.push(u);
}
}
int shortest=n+1;
while(!pending.empty()){
int u=pending.front();
pending.pop();
if(distance[u]>=shortest){
continue;
}
for(int v:graph[u]){
if(mate[v]==-1){
shortest=distance[u];
}
else if(distance[mate[v]]==-1){
distance[mate[v]]=distance[u]+1;
pending.push(mate[v]);
}
}
}
if(shortest==n+1){
break;
}
function<bool(int)>augment=[&](int u){
for(int v:graph[u]){
bool ends=mate[v]==-1&&distance[u]==shortest;
bool continues=mate[v]!=-1&&distance[mate[v]]==distance[u]+1&&augment(mate[v]);
if(ends||continues){
mate[u]=v;
mate[v]=u;
return true;
}
}
distance[u]=-1;
return false;
};
for(int u:left){
if(mate[u]==-1){
augment(u);
}
}
}
// Alternating reachability gives cover = (left not reached) union (right reached).
vector<int>reached(n),isLeft(n);
queue<int>pending;
for(int u:left){
isLeft[u]=1;
if(mate[u]==-1){
reached[u]=1;
pending.push(u);
}
}
while(!pending.empty()){
int u=pending.front();
pending.pop();
if(isLeft[u]){
for(int v:graph[u]){
if(mate[u]!=v&&!reached[v]){
reached[v]=1;
pending.push(v);
}
}
}
else if(mate[u]!=-1&&!reached[mate[u]]){
reached[mate[u]]=1;
pending.push(mate[u]);
}
}
vector<int>cover,independent,isolated;
for(int u=0;u<n;++u){
if(graph[u].empty()){
isolated.push_back(u);
}
else if((isLeft[u]&&!reached[u])||(!isLeft[u]&&reached[u])){
cover.push_back(u);
}
else{
independent.push_back(u);
}
}
int repetitions=moves/2+1;
long long shots=isolated.size()+1LL*repetitions*(cover.size()+independent.size());
if(moves%2==1){
shots+=cover.size();
}
cout<<shots<<'\n';
auto fire=[&](const vector<int>&vertices){
for(int u:vertices){
cout<<cell[u].first<<' '<<cell[u].second<<'\n';
}
};
fire(isolated);
for(int pass=0;pass<repetitions;++pass){
fire(cover);
fire(independent);
}
if(moves%2==1){
fire(cover);
}
}