voidBFS() { int front = 0, rear = 0; BFSQueue[rear++] = {{-1, Steve, 0}, 1, -1, 0};
while (front < rear) { BFSEventList current = BFSQueue[front++]; for (char i = 0; i < 6; i++) { for (char j = 0; j < 3; j++) { if (EventList[current.currentEvent.to][i][j] == true) { Event constraint = EventConstraint[current.currentEvent.to][i][j]; if (constraint.from != -1) { if (!CheckConstraintHappened(constraint, front - 1)) continue; }
BFSEventList next; next.currentEvent = {current.currentEvent.to, i, j}; next.eventCount = current.eventCount + 1; next.previousEventIndex = front - 1;
// check critical event and character next.CriticalEvent = current.CriticalEvent | isCriticalEvent(next.currentEvent); BFSQueue[rear++] = next; if (rear >= MAXLEN) break;
// check target achieved if (i == Steve && next.CriticalEvent == ALL_EVENTS) { finaleEventIndex = rear - 1; return; } } } } if (rear > MAXLEN) break; } cout << rear << endl; cout << BFSQueue[MAXLEN].eventCount << endl; }
charisCriticalEvent(const Event &event) { if (event.from == Creeper && event.to == Steve && event.eventID == 1) return CS1; if (event.from == Diamond && event.to == Steve && event.eventID == 2) return DS2; if (event.from == Enderman && event.to == Steve && event.eventID == 1) return ES1; if (event.from == Enderman && event.to == Golem && event.eventID == 0) return EG; if (event.from == Villager && event.to == Diamond && event.eventID == 1) return VD1; if (event.from == Golem && event.to == Steve && event.eventID == 1) return GS1; return0; }
voidBFS() { int front = 0, rear = 0; BFSQueue[rear++] = {{-1, Steve, 0}, 1, -1, 0};
while (front < rear) { BFSEventList current = BFSQueue[front++]; for (char i = 0; i < 6; i++) { for (char j = 0; j < 3; j++) { if (EventList[current.currentEvent.to][i][j] == true) { Event constraint = EventConstraint[current.currentEvent.to][i][j]; if (constraint.from != -1) { if (!CheckConstraintHappened(constraint, front - 1)) continue; }
BFSEventList next; next.currentEvent = {current.currentEvent.to, i, j}; next.eventCount = current.eventCount + 1; next.previousEventIndex = front - 1;
// check critical event and character next.CriticalEvent = current.CriticalEvent | isCriticalEvent(next.currentEvent); BFSQueue[rear++] = next; if (rear >= MAXLEN) break;
// check target achieved if (i == Steve && next.CriticalEvent == ALL_EVENTS) { finaleEventIndex = rear - 1; return; } } } } if (rear > MAXLEN) break; } cout << rear << endl; cout << BFSQueue[MAXLEN].eventCount << endl; }
voidCheckResult() { if (finaleEventIndex == -1) { cout << "Impossible" << endl; return; } vector<Event> resultEvents; int idx = finaleEventIndex; while (idx != -1) { BFSEventList event = BFSQueue[idx]; resultEvents.push_back(event.currentEvent); idx = event.previousEventIndex; } reverse(resultEvents.begin(), resultEvents.end()); cout << resultEvents.size() - 1 << endl; for (size_t i = 1; i < resultEvents.size(); i++) { Event event = resultEvents[i]; char fromChar, toChar; switch (event.from) { case Steve: fromChar = 'S'; break; case Creeper: fromChar = 'C'; break; case Diamond: fromChar = 'D'; break; case Enderman: fromChar = 'E'; break; case Villager: fromChar = 'V'; break; case Golem: fromChar = 'G'; break; } switch (event.to) { case Steve: toChar = 'S'; break; case Creeper: toChar = 'C'; break; case Diamond: toChar = 'D'; break; case Enderman: toChar = 'E'; break; case Villager: toChar = 'V'; break; case Golem: toChar = 'G'; break; } cout << "(" << fromChar << toChar; if (event.eventID > 0) cout << event.eventID; cout << ")" << endl; } }
Events are coded like (ABx), where A is the initiator character, B is the target character, and x is the event ID (if multiple events exist between the same characters). Omit x if x=0. Event whose x is 1 or 2 has constraint.
