#define FOR(i,n) for(int i=0; i<(n); i++)
typedef vector VI;
struct CrazySwitches {
int minimumActions(vector s) {
int n = s.size();
int N = (1<<n);
VI v(N * n, 999999); // idx = N * room + on bits
v[1] = 0;
queue q;
q.push(1);
while (!q.empty()) {
int t = q.front(); q.pop();
int on = t % N, r = t / N;
FOR(i, n) {
if (s[i] == r && i != r) { // can switch
int tt = t ^ (1<<i);
if (v[tt] > v[t]) v[tt] = v[t], q.push(tt);
}
}
FOR(i, n) if (i != r) {
if ((on & (1<<i)) == 0) continue; // cannot move to this room
int tt = on + i * N;
if (v[tt] > v[t] + 1) v[tt] = v[t] + 1, q.push(tt);
}
}
int ret = v[(n-1) * N + (1 << (n-1))];
return ret == 999999 ? -1 : ret;
}
};
[^] # Re: Question bête
Posté par Philippe F (site web personnel) . En réponse au journal Topcoder. Évalué à 2.
#define FOR(i,n) for(int i=0; i<(n); i++) typedef vector VI; struct CrazySwitches { int minimumActions(vector s) { int n = s.size(); int N = (1<<n); VI v(N * n, 999999); // idx = N * room + on bits v[1] = 0; queue q; q.push(1); while (!q.empty()) { int t = q.front(); q.pop(); int on = t % N, r = t / N; FOR(i, n) { if (s[i] == r && i != r) { // can switch int tt = t ^ (1<<i); if (v[tt] > v[t]) v[tt] = v[t], q.push(tt); } } FOR(i, n) if (i != r) { if ((on & (1<<i)) == 0) continue; // cannot move to this room int tt = on + i * N; if (v[tt] > v[t] + 1) v[tt] = v[t] + 1, q.push(tt); } } int ret = v[(n-1) * N + (1 << (n-1))]; return ret == 999999 ? -1 : ret; } };