Hamming Path
InterviewTime limit1sMemory limit128 MB
Build a graph where binary codes connect if their Hamming distance is 1, then output a shortest path between two given codes via BFS.
Problem
The Hamming distance between two binary codes of the same length is the number of positions where their bits differ.
You are given N distinct binary codes, and every code has length K. The codes are numbered from 1 to N in the order they are given.
A Hamming path is a sequence of code numbers where each neighboring pair in the sequence has Hamming distance exactly 1.
Given two different code numbers A and B, find a shortest Hamming path from A to B.
Input
The first line contains two integers N and K (3 <= N <= 1,000, 2 <= K <= 30).
Each of the next N lines contains one binary code of length K, with no spaces. All codes are distinct and are numbered from 1 to N in input order.
The last line contains two different code numbers A and B.
Output
If a Hamming path exists between the two given codes, print the code numbers on any shortest such path from A to B, separated by single spaces.
If there is more than one shortest path, print any one of them. If no path exists, print -1.