백준 2479
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
stack<int> s;
queue<int> q;
int arr[1010][40], graph[1010][1010], n, k, answer, start1, end1;
int parent[1010];
void bfs(int idx) {
int j = 0;
for (int i = 1; i <= n; i++) {
if (graph[idx][i] != 0) {
q.push(i);
if (i == end1) {
answer = 1;
s.push(i);
}
parent[i] = start1;
}
}
while (!q.empty()) {
int index = q.front(); q.pop();
for (int i = 1; i <= n; i++) {
if (parent[i] == 0 && graph[index][i] != 0) {
parent[i] = index;
if (i == end1) {
answer = 1;
while (parent[i] != -1) {
s.push(i);
i = parent[i];
}
}
q.push(i);
}
}
}
}
int main() {
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
char a;
scanf(" %c", &a);
arr[i][j] = a - '0';
}
}
scanf("%d %d", &start1, &end1);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int diff = 0;
for (int index = 0; index < k; index++) {
if (arr[i][index] != arr[j][index]) diff++;
}
if (diff == 1) {
graph[i + 1][j + 1] = 1;
graph[j + 1][i + 1] = 1;
}
}
}
parent[start1] = -1;
bfs(start1);
if (answer == 0) printf("-1");
else {
printf("%d ", start1);
while (!s.empty()) {
int n = s.top();
printf("%d ", n);
s.pop();
}
}
}
