提出 #67768

---

ソースコード 拡げる

// include {{{
#include <cstdio>
#include <iostream>
//#include <sstream>
#include <string>
#include <vector>
//#include <deque>
#include <stack>
#include <queue>
//#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <numeric>
//#include <complex>
// }}}
using namespace std;
// macro {{{
typedef long long ll;
typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(n);++i)
#define REP(i,j,k) for(int i=j;i<(k);++i)
//#define foreach(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();++it)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define priority_queue_greater(T) priority_queue< T, vector<T>, greater<T> >
#define F first
#define S second
//test define...
#define D(x) #x<<"="<<(x)
#define CC <<" "<<
#define CE <<endl;
// }}}

string first,last;
int n;
int main(){
  while( cin >> first >> last >> n ){
    int size = first.size();
    int N = n+2;
    vector<string> s(N);
    s[0] = first;
    s[n+1] = last;
    rep(i,n){ cin >> s[i+1]; }

    mat edges(N);
    rep(i,N)REP(j,i+1,N){
      int diff = 0;
      rep(k,size)if( s[i][k] != s[j][k] ){ diff++; }
      if( diff <= 1 ){
        edges[i].push_back(j);
        edges[j].push_back(i);
      }
    }

    vec memo(N, -1);
    queue<int> qn, qp;
    qn.push(0);
    qp.push(-2);
    while( !qn.empty() ){
      int now = qn.front(); qn.pop();
      int prev= qp.front(); qp.pop();

      if( memo[now] != -1 ){ continue; }
      memo[now] = prev;
      if( now == N-1 ){ break; }

      int len = edges[now].size();
      rep(i,len){
        int next = edges[now][i];
        if( memo[next] == -1 ){
          qn.push( next );
          qp.push( now );
        }
      }
    }

    if( memo[n+1] == -1 ){
      cout << -1 << endl;
    }else{
      int sum = -2;
      int now = n+1;
      vector<string> ans;
      while( now != -2 ){
        sum++;
        ans.push_back( s[now] );
        now = memo[now];
      }
      cout << sum << endl;
      for(int i=ans.size()-1; i>=0; i--){
        cout << ans[i] << endl;
      }
    }
  }
  return 0;
}

提出情報

ジャッジ結果