UVA 10047 The Monocycle：帶顏色與方向狀態的 BFS

題目大意

單輪車輪子分 5 色扇區，每前進一格輪子旋轉 72°（換一色）。可原地左/右轉 90°。起點 S 朝北、綠色觸地。終點 T 需綠色觸地，方向任意。求最短時間（每動作 1 秒）。網格 ≤ 25×25。

狀態定義

(x, y, color, dir)：位置、當前觸地顏色（0-4）、面向方向（0:北,1:東,2:南,3:西）。狀態數 ≤ 25×25×5×4 = 12500。

BFS 轉移

• 前進：nx=x+dx[dir], ny=y+dy[dir], ncolor=(color+1)%5
• 左轉：ndir=(dir+3)%4，顏色不變
• 右轉：ndir=(dir+1)%4，顏色不變

起始狀態 (sx, sy, 0, 0)。目標：grid[x][y]=='T' && color==0。

代碼片段

struct Node { int x,y,c,d,step; };
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool vis[25][25][5][4];
int bfs() {
    memset(vis,0,sizeof(vis));
    queue<Node> q; q.push({sx,sy,0,0,0}); vis[sx][sy][0][0]=1;
    while(!q.empty()) {
        Node cur=q.front(); q.pop();
        if (grid[cur.x][cur.y]=='T' && cur.c==0) return cur.step;
        // 前進
        int nx=cur.x+dir[cur.d][0], ny=cur.y+dir[cur.d][1], nc=(cur.c+1)%5;
        if (inmap(nx,ny) && !vis[nx][ny][nc][cur.d]) {
            vis[nx][ny][nc][cur.d]=1; q.push({nx,ny,nc,cur.d,cur.step+1});
        }
        // 左/右轉
        for (int nd : {(cur.d+3)%4, (cur.d+1)%4}) {
            if (!vis[cur.x][cur.y][cur.c][nd]) {
                vis[cur.x][cur.y][cur.c][nd]=1; q.push({cur.x,cur.y,cur.c,nd,cur.step+1});
            }
        }
    }
    return -1;
}

關鍵細節

• 方向順序必須按順時針：北、東、南、西，對應轉向計算。
• 輸出格式：Case #i，中間空行。