图上的远足游戏题解

问题描述

这是一个在完全图上进行的三人游戏。图中每条边都有颜色，三个棋子初始位于不同的位置。每次移动一个棋子时，必须选择与另外两个棋子之间边颜色相同的边进行移动。目标是通过最少次数的移动，使得三个棋子位于同一个顶点上。

解题思路

1. 广度优先搜索(BFS)：使用BFS来探索所有可能的棋子位置组合，确保找到最短路径
2. 状态表示：用三元组(p1,p2,p3)表示三个棋子的位置状态
3. 移动规则：每次只能移动一个棋子，且移动边的颜色必须等于另外两个棋子所在顶点间边的颜色
4. 终止条件：当三个棋子位于同一顶点时终止搜索

代码解析

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;

const int N = 55;
char mp[N][N]; // 邻接矩阵存储边的颜色
bool vis[N][N][N]; // 访问标记数组
int n; // 顶点数
struct Node {
    int p[3]; // 三个棋子的位置
    int t; // 移动步数
};
int p[3]; // 初始位置

// 检查是否达到目标状态(三个棋子在同一位置)
bool ok(Node nx) {
    return nx.p[0] == nx.p[1] && nx.p[0] == nx.p[2];
}

int bfs() {
    queue<Node> q;
    mem(vis,0); // 初始化访问数组
    
    Node h;
    for(int i=0; i<3; ++i) h.p[i] = p[i];
    h.t = 0;
    vis[h.p[0]][h.p[1]][h.p[2]] = 1; // 标记初始状态
    q.push(h);
    
    while(!q.empty()) {
        h = q.front();
        q.pop();
        int a=h.p[0], b=h.p[1], c=h.p[2];
        
        // 尝试移动每个棋子
        for(int i=1; i<=n; ++i) {
            // 移动棋子a到i的条件：边a-i的颜色等于边b-c的颜色
            if(mp[a][i] == mp[b][c] && !vis[i][b][c]) {
                Node nx = h;
                nx.p[0] = i;
                nx.t++;
                if(ok(nx)) return nx.t; // 检查是否达到目标
                vis[i][b][c] = 1;
                q.push(nx);
            }
            
            // 移动棋子b到i的条件：边b-i的颜色等于边a-c的颜色
            if(mp[b][i] == mp[a][c] && !vis[a][i][c]) {
                Node nx = h;
                nx.p[1] = i;
                nx.t++;
                if(ok(nx)) return nx.t;
                vis[a][i][c] = 1;
                q.push(nx);
            }
            
            // 移动棋子c到i的条件：边c-i的颜色等于边a-b的颜色
            if(mp[c][i] == mp[a][b] && !vis[a][b][i]) {
                Node nx = h;
                nx.p[2] = i;
                nx.t++;
                if(ok(nx)) return nx.t;
                vis[a][b][i] = 1;
                q.push(nx);
            }
        }
    }
    return -1; // 无法达到目标状态
}

int main() {
    while(~scanf("%d",&n)) {
        if(!n) break;
        cin >> p[0] >> p[1] >> p[2];
        
        // 读取图的边颜色信息
        for(int i=1; i<=n; ++i) {
            for(int j=1; j<=n; ++j) {
                cin >> mp[i][j];
            }
        }
        
        // 初始状态检查
        if(p[0]==p[1] && p[0]==p[2]) {
            puts("0");
            continue;
        }
        
        int ans = bfs();
        if(ans == -1) {
            puts("impossible");
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}

关键点解析

1. 状态表示：使用三维数组vis[N][N][N]来记录三个棋子的位置状态是否已被访问
2. 移动规则：每次移动必须满足移动边的颜色等于另外两个棋子所在顶点间边的颜色
3. BFS搜索：保证找到的解决方案是最短路径
4. 终止条件：当三个棋子位置相同时立即返回当前步数

复杂度分析

• 时间复杂度：O(n³)，因为最坏情况下需要探索所有可能的三元组状态
• 空间复杂度：O(n³)，用于存储访问标记数组

该算法有效地解决了这个图上的移动问题，通过BFS确保了找到最短路径，同时使用状态标记避免了重复计算。