問題
オートマトン図が与えられ、各状態について１～４までの数字が与えられた時に遷移する状態が与えられる。
例） １行目：１ ２ ２ ３
状態０が１～４を与えられた時に遷移する状態
すべての要素の初期状態についてわかっていないとき、
すべての要素が同じ状態になるために必要な最小の遷移回数を求める。
解き方
すべての状態の初期状態が不明なので、最悪の場合、つまり各要素が異なる状態を持っていることを考える。
要素数は２０なので、各要素の状態数は全探索可能。
よってメモ化を用いて、ＢＦＳにて答えを求める。
ＤＦＳの場合は深さ優先探索にて最小の長さを求められないケースも発生しうるので、
うまくいかない。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[1300000],p[30][4],n,ans;
class SequenceSync {
public:
bool ispossible(int x){
int cnt=0;
FORE(i,0,n)if(x&(1<<i))cnt++;
return cnt==1;
}
int getLength(vector<string> transitions) {
n=transitions.size();
ans=1e+9;
if(n==1)return 0;
FORE(i,0,n){
stringstream out(transitions[i]);
out>>p[i][0]>>p[i][1]>>p[i][2]>>p[i][3];
}
memset(dp,-1,sizeof(dp));
queue<int> q;
q.push((1<<n)-1);
dp[(1<<n)-1]=0;
while(!q.empty()){
int cur=q.front();
q.pop();
FORE(i,0,4){
int next=0;
FORE(j,0,n)if(cur&(1<<j))next|=(1<<p[j][i]);
if(dp[next]!=-1)continue;
dp[next]=dp[cur]+1;
if(ispossible(next))return dp[next];
q.push(next);
}
}
return -1;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[1300000],p[30][4],n,ans;
class SequenceSync {
public:
bool ispossible(int x){
int cnt=0;
FORE(i,0,n)if(x&(1<<i))cnt++;
return cnt==1;
}
int getLength(vector<string> transitions) {
n=transitions.size();
ans=1e+9;
if(n==1)return 0;
FORE(i,0,n){
stringstream out(transitions[i]);
out>>p[i][0]>>p[i][1]>>p[i][2]>>p[i][3];
}
memset(dp,-1,sizeof(dp));
queue<int> q;
q.push((1<<n)-1);
dp[(1<<n)-1]=0;
while(!q.empty()){
int cur=q.front();
q.pop();
FORE(i,0,4){
int next=0;
FORE(j,0,n)if(cur&(1<<j))next|=(1<<p[j][i]);
if(dp[next]!=-1)continue;
dp[next]=dp[cur]+1;
if(ispossible(next))return dp[next];
q.push(next);
}
}
return -1;
}
};