Chess
National Olympiad · Municipal round
Submission name: chess.cpp
Problem summary
Two knights start on different squares of a standard 8×8 board. Both must make one legal knight move each second. Find the earliest time they can occupy the same square, or report impossibility.
Input
T, followed by T pairs of algebraic square coordinates, such as a1 h8.
Output
For each case, print the minimum seconds or −1.
Constraints
1 ≤ T ≤ 10; coordinates are valid; the two starting squares differ.
Worked example
An independently prepared example for this explanation.
Input
2 a1 c1 a1 b1
Output
1 -1
Solution analysis
- Treat the 64 squares as graph vertices; connect squares separated by a legal knight move.
- Run BFS from each knight’s start to obtain shortest distances to every square.
- They can meet at a square only when both distances have the same parity: every move changes the square color.
- A knight can add any even number of moves by traversing an edge and immediately returning. Therefore the earliest meeting at a parity-compatible square is max(d1,d2). Minimize this over all squares.
Why it works
A meeting cannot precede either knight’s shortest distance. Equal parity lets the earlier knight add back-and-forth pairs to reach the same square at the later distance. Every board square has a legal neighbor, so these extra pairs are always possible.
Watch out. Neither knight may simply wait. Opposite-colored starts remain opposite-colored at every simultaneous step.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: A meeting cannot precede either knight’s shortest distance. Equal parity lets the earlier
// knight add back-and-forth pairs to reach the same square at the later distance.
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;
vector<int>bfs(const vector<vector<int>>&g,int start){
vector<int>d(64,-1);
queue<int>q;
d[start]=0;
q.push(start);
while(!q.empty()){
int v=q.front();
q.pop();
for(int u:g[v]){
if(d[u]==-1){
d[u]=d[v]+1;
q.push(u);
}
}
}
return d;
}
int square(const string&s){
return (s[1]-'1')*8+(s[0]-'a');
}
int main(){
vector<vector<int>>g(64);
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
for(int y=0;y<8;++y){
for(int x=0;x<8;++x){
for(int k=0;k<8;++k){
int nx=x+dx[k],ny=y+dy[k];
if(0<=nx&&nx<8&&0<=ny&&ny<8){
g[y*8+x].push_back(ny*8+nx);
}
}
}
}
int t;
cin>>t;
while(t--){
string a,b;
cin>>a>>b;
auto d1=bfs(g,square(a)),d2=bfs(g,square(b));
int answer=1000000;
for(int v=0;v<64;++v){
if(d1[v]>=0&&d2[v]>=0&&(d1[v]-d2[v])%2==0){
answer=min(answer,max(d1[v],d2[v]));
}
}
cout<<(answer==1000000?-1:answer)<<'\n';
}
}