题意分析

在魔法王国中，存在着双向的魔法传送门网络。这些传送门连接着城市，使人们能够在城市间快速旅行和交流。王子阿尔伯特（Albert）和公主贝蒂（Betty）居住在相邻城市，他们深爱着彼此，必须时刻保持相邻，并且不敢同时出现在同一城市。他们可以同时通过一对传送门移动到另一对相邻城市，也可以其中一人移动而另一人留在原地，但不能同时通过同一传送门。现在需要编写一个程序，帮助他们从初始的相邻城市对移动到目标的相邻城市对，并且要找到移动次数最少的方案，同时输出移动次数、经过的相邻城市对数量以及具体的相邻城市对序列。

问题核心

问题的核心在于找到从起始相邻城市对到目标相邻城市对的最短路径，其中最短路径的衡量标准是通过魔法传送门的最少移动次数。需要考虑各种移动的可能性（两人同时移动、一人移动一人不动），并且要保证在移动过程中两人始终处于相邻城市，同时避免两人同时通过同一传送门。

解题思路

可以使用广度优先搜索（BFS）算法来解决这个问题。BFS 算法非常适合用于寻找最短路径问题。 构建图：根据输入的城市和传送门信息，构建一个图来表示城市之间的连接关系。

定义状态：每个状态可以用一个三元组 (albert_city, betty_city, moves) 来表示，其中 albert_city 和 betty_city 分别表示阿尔伯特和贝蒂所在的城市，moves 表示到当前状态为止的移动次数。 初始化队列和访问集合：将起始状态加入队列，并将其标记为已访问。

BFS 搜索： 从队列中取出一个状态。 生成所有可能的下一步状态，考虑两人同时移动和一人移动一人不动的情况，同时要保证两人始终相邻且不通过同一传送门。 对于每个新状态，如果未被访问过，则将其加入队列并标记为已访问，同时记录其父状态以便后续回溯路径。

找到目标状态：当找到目标状态时，停止搜索。 回溯路径：根据记录的父状态，从目标状态回溯到起始状态，得到完整的路径。

代码

#include <cstring>
#include <queue>
 
using namespace std;
 
const int maxn = 100 + 10;
const int maxp = 10000 + 10;
 
int G[maxn][maxn], n, m, a1, b1, a2, b2;        //G为邻接矩阵
int d[maxn][maxn];      //d[i][j]为到达组合(i, j)时最少要经过多少个组合
int step[maxn][maxn];       //总步数
bool vis[maxn][maxn];       //bfs用
 
struct Pair{
    int A, B;
    bool operator < (const Pair& e) const{
        return step[A][B] > step[e.A][e.B];
    }
}fa[maxn][maxn];        //fa[i][j]组合(i, j)的上一步在哪
 
void init(){
    memset(vis, 0, sizeof(vis));
    d[a1][b1] = 1;
    step[a1][b1] = 0;
}
 
void bfs(){
    init();
    priority_queue<Pair> qu;
    qu.push((Pair){a1, b1});
    vis[a1][b1] = 1;
    while(!qu.empty()){
        Pair p = qu.top(); qu.pop();
        for(int i = 1; i <= n; i++) if(G[p.A][i]){
            for(int j = 1; j <= n; j++) if(G[p.B][j] && G[i][j] && i != j){
                if(i == p.B && j == p.A) continue;
                int temp;
                if(i != p.A && j != p.B) temp = step[p.A][p.B] + 2;
                else temp = step[p.A][p.B] + 1;
                if(vis[i][j] && temp >= step[i][j]) continue;
                qu.push((Pair){i, j});
                d[i][j] = d[p.A][p.B] + 1;
                step[i][j] = temp;
                fa[i][j] = (Pair){p.A, p.B};
                vis[i][j] = 1;
            }
        }
    }
}
 
Pair ret[maxp];
int getRet(){
    int i = 0, x = a2, y = b2;
    while(x != a1 || y != b1){
        ret[i++] = (Pair){x, y};
        int tx = fa[x][y].A;
        int ty = fa[x][y].B;
        x = tx;
        y = ty;
    }
    ret[i++] = (Pair){a1, b1};
    return i;
}
 
int main()
{
    int u, v;
    while(scanf("%d%d%d%d%d%d", &n, &m, &a1, &b1, &a2, &b2) == 6){
        memset(G, 0, sizeof(G));
        for(int i = 1; i <= n; i++) G[i][i] = 1;
        for(int i = 1; i <= m; i++){
            scanf("%d%d", &u, &v);
            G[u][v] = G[v][u] = 1;
        }
        bfs();
        printf("%d %d\n", step[a2][b2], d[a2][b2]);
        int cnt = getRet();
        for(int i = cnt-1; i >= 0; i--) printf("%d %d\n", ret[i].A, ret[i].B);
    }
    return 0;
}