好的，以下是包含原代码在内的完整题解文档，适合作为整理或提交说明使用。

🚗 Rush Hour 题解（含完整 C++ 实现）

💡 题目描述

Rush Hour 是一个经典的滑块谜题。我们在一个 6×6 的网格中模拟交通拥堵，目标是将玩家的车（用字母 'x' 表示）从网格左侧出发，移出右侧边界。车只能在自己的方向上移动（水平或垂直），不能穿越其他车辆或越界。每次只能移动一辆车，可以移动任意距离（只要路径畅通），求使 'x' 车成功逃离的最小步数。

📥 输入格式

每组场景以一个整数 n 开头（表示车辆数量），后跟 6 行，每行 6 个字符，表示初始网格布局：

• "." 表示空格；
• "x" 表示玩家的车（始终为横向）；
• 其他小写字母表示不同的车或卡车（1 格宽，2~3 格长）。

输入以 0 结束。

📤 输出格式

对于每组场景，输出格式如下：

• 若可以成功逃离，输出：

  Scenario #K requires X moves.
  

• 否则输出：

  You are trapped in scenario #K.
  

🧠 解题思路

• 使用广度优先搜索（BFS）从起始状态出发，探索每种可能的车辆移动方式。
• 通过哈希表存储访问状态，避免重复搜索。
• 每次移动一辆车，沿方向前进或后退多个格子，更新状态。
• 当玩家车辆可以滑出右边界时，即可得出最短步数。

🔧 数据结构设计

• Car：表示每辆车的起始坐标、方向（水平/垂直）、长度；
• State：表示一种全局布局状态，包括每辆车的位置、方向、占用的格子、步数；
• 哈希表：用于状态去重，加快搜索效率。

✅ 判断结束条件

函数 finish 用于判断 'x' 车是否可以无障碍地滑出右边界。

💻 C++ 实现代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
 
#define MOD 89991  //自己根据需要改大小
#define LL long long
int Move[2][4] = { { 0,1,0,-1},{1,0,-1,0} };
int n , Cas;
char maze[7][7];
bool b[26];
 
inline bool inRange(int r,int c)
{
        return 0 <= r && r < 6 && 0 <= c && c < 6;
}
 
struct Car
{
        int r , c;
        int dir , len;
};
 
struct State
{
        bool vis[6][6];
        Car car[10];
        State * next;
        int step;
}vis[MOD] , *first[MOD] , start;
int sz;
 
 
int hashcode(const State & s)
{
        LL ret = 0;
        for (int i = 0 ; i < n ; ++i)
        {
                ret += 1313L*((LL)s.car[i].r*131313^s.car[i].c*13131313)<<2;
                ret %= MOD;
        }
        return ret;
}
 
bool equals(const State & s1 , const State & s2)
{
        for (int i = 0 ; i < n ; ++i) 
        {
                if (s1.car[i].r!=s2.car[i].r || s1.car[i].c!=s2.car[i].c) return false;
        }
        return true;
}
 
 
bool in_vis(const State & s)
{
        int k = hashcode(s);
        State * p = first[k];
        while (p)
        {
                if (equals(s,*p)) return true;
                p = p->next;
        }
        return false;
}
 
void add(const State & s)
{
        vis[sz] = s;
        int k = hashcode(s);
        vis[sz].next = first[k];
        first[k] = &vis[sz];
        ++sz;
}
 
void init()
{
        memset(first,0,sizeof(first));
        memset(vis,0,sizeof(vis));
        sz = 0;
}
 
void input()
{
        for (int i = 0 ; i < 6 ; ++i)
                scanf("%s",maze[i]);
        memset(start.vis,0x3f,sizeof(start.vis));
        memset(b,0,sizeof(b));
        int size = 1;
        start.step = 0;
        for (int i = 0 ; i < 6 ; ++i)
        {
                for (int j = 0 ; j < 6 ; ++j)
                {
                        if (maze[i][j]=='.') continue;
                        start.vis[i][j] = false;
                        if (b[maze[i][j]-'a']) continue;
                        b[maze[i][j]-'a'] = true;
                        int Index = maze[i][j]=='x' ? 0 : size++;
                        Car & veh = start.car[Index];
                        veh.len = 1;
                        veh.r = i , veh.c = j;
                        while (inRange(i,j+veh.len) && maze[i][j]==maze[i][j+veh.len])
                        {
                                start.vis[i][j+veh.len] = false;
                                ++veh.len;
                        }
                        if (veh.len != 1)
                        {
                                veh.dir = 0;
                                continue;
                        }
                        while (inRange(i+veh.len,j) && maze[i][j]==maze[i+veh.len][j])
                        {
                                start.vis[i+veh.len][j] = false;
                                ++veh.len;
                        }
                        veh.dir = 1;
                }
        }
        add(start);
}
 
bool finish(const State & s)
{
        int dir = s.car[0].dir , len = s.car[0].len , r = s.car[0].r , c = s.car[0].c;
        int i = r+Move[0][dir]*len , j = c+Move[1][dir]*len;
        bool ok = true;
        while (inRange(i,j))
        {
                if (!s.vis[i][j]) 
                {
                        ok = false;
                        break;
                }
                i += Move[0][dir];
                j += Move[1][dir];
        }
        return ok;
}
 
void solve()
{
        if (start.car[0].dir==1) 
        {
                printf("You are trapped in scenario #%d.\n",Cas);
                return;
        }
        queue<State> q;
        q.push(start);
        while (q.size())
        {
                State tmp = q.front(); q.pop();
                for (int i = 0 ; i < n ; ++i)
                {
                        State now = tmp;
                        ++now.step;
                        int len = now.car[i].len , d = now.car[i].dir;
                        int & r1 = now.car[i].r;
                        int & c1 = now.car[i].c;
                        int r2 = r1+(len-1)*Move[0][d];
                        int c2 = c1+(len-1)*Move[1][d];
                        while (inRange(r2,c2))
                        {
                                r2 += Move[0][d];
                                c2 += Move[1][d];
                                if (!inRange(r2,c2) || !now.vis[r2][c2]) break;
                                now.vis[r1][c1] = true;
                                r1 += Move[0][d];
                                c1 += Move[1][d];
                                now.vis[r2][c2] = false;
                                if (!in_vis(now)) 
                                {
                                        if (i > 0 && finish(now))
                                        {
                                                printf("Scenario #%d requires %d moves.\n",Cas,now.step+1);
                                                return;
                                        }
                                        q.push(now);
                                        add(now);
                                }
                        }
                        now = tmp;
                        r1 = now.car[i].r;
                        c1 = now.car[i].c;
                        r2 = r1+(len-1)*Move[0][d];
                        c2 = c1+(len-1)*Move[1][d];
                        d = (d+2)%4;
                        ++now.step;
                        while (inRange(r1,c1))
                        {
                                r1 += Move[0][d];
                                c1 += Move[1][d];
                                if (!inRange(r1,c1) || !now.vis[r1][c1]) break;
                                now.vis[r1][c1] = false;
                                now.vis[r2][c2] = true;
                                r2 += Move[0][d];
                                c2 += Move[1][d];
                                if (!in_vis(now))
                                {
                                        if (i > 0 && finish(now))
                                        {
                                                printf("Scenario #%d requires %d moves.\n",Cas,now.step+1);
                                                return;
                                        }
                                        q.push(now);
                                        add(now);
                                }
                        }
                }
        }
        printf("You are trapped in scenario #%d.\n",Cas);
}
 
int main()
{
        while (scanf("%d",&n),n)
        {
                ++Cas;
                init();
                input();
                solve();
        }
}

📌 样例输入输出

输入

8
aa...b
c..d.b
cxxd.b
c..d..
e...ff
e.ggg.
8
abbc..
a..c..
axxc..
..gddd
..g..e
..fffe
0

输出

Scenario #1 requires 8 moves.
Scenario #2 requires 25 moves.

如需，我可以为此算法生成一个车辆移动动画或图示说明。你希望我画出状态图或搜索过程图吗？