[UVA] 816 - Abbott's Revenge

題目連結
題目說明：
給定一個9*9的迷宮，給一起點和終點，起點有給起始方向，求最短路徑。
迷宮的每一個點有給固定的條件只能往哪邊走，
例如：
2 3 SFR EL *
就是指當拜訪到(2, 3)這個點若是往S(南邊)則只能往前走或往右走，
如果是往E(東邊)則只能往左走。
==============================
我的作法：
因為到每個點都需要考慮往哪個方向應該往哪邊走，
我直接將每一個點都設置NESW四個方位，重新定義點與點之間的連線，
例如下圖中藍線就是點與點可以走的路，[1]→[40]就是1可以走到40，依此類推。
起點的位置需要注意，若測資是3 1 N 3 3，從3 1位置往N走，所以起點是2 1哦！
終點的位置因為有4個方向所以有4個，4個都當終點跑一次，找到最短的才是答案。
接下來就可以快樂地用BFS，有起點，有終點，求最短路徑不是夢!

需要注意的幾個點是：

• 最後要記得補上真的起點。
• BFS判斷是否有解可以看兩點
• 起點終點同一個 => 有解
• 路徑在儲存的時候>1個 => 有解

==============================
程式碼：

/* 題目: UVa 816 - Abbott's Revenge
 * Language: C++
 * Created on: 2017年07月15日
 *   Author: hanting
 */
 //注意的點，路徑必須要最短
 //起點終點一樣
 //起點下一步就是終點
 //起點可以走到終點，可是起始方向不是終點方向
#include <iostream>
#include <cstring> // memset
#include <stack>
#include <vector>
using namespace std;
#define row 10
#define col 10
#define pos(i, j, dir) (i-1)*row*4 + (j-1)*4 + dir
enum
{
    N, E, S, W
};
enum
{
    F, L, R
};
class BFS
{
    vector<vector<int> > adjList;
public:
    vector<int> shortestPath;
    BFS(vector<vector<int> > &_adjList)
    {
        adjList = _adjList;
    }
    void findShortestPath(int start, int goal)
    {
        shortestPath.clear();
        vector<int> cur, next;
        cur.push_back(start);
        vector<int> visit(adjList.size(), -1); // visit[n] = m; // n點是透過m點拜訪到的
        while(cur.size())
        {
            for(int i = 0; i < cur.size(); i++)
            {
                int tmp = cur[i]; // 該層某一點
                for(int j = 0; j < adjList[tmp].size(); j++)
                {
                    int sub = adjList[tmp][j]; // 該層某一點的子節點
                    if(sub != start && visit[sub] == -1)
                    {
                        visit[sub] = tmp;
                        next.push_back(sub);
                    }
                }
            }
            cur = next;
            next.clear();
        }
        shortestPath.push_back(goal);
        int tmp = visit[goal];
        while(tmp != -1)
        {
            shortestPath.push_back(tmp);
            tmp = visit[tmp];
        }
    }
};
int main()
{
    string mazeName;
    while(getline(cin, mazeName) && mazeName != "END")
    {
        int start_i, start_j, goal_i, goal_j, start, goal;
        char face;
        vector<vector<int> > adjList(row*col*4, vector<int>());
        // 1 1 NESW 分別為0 1 2 3 4
        // [n, n] = adjList的index (n-1)*9+(n-1)
        cin >> start_i >> start_j >> face >> goal_i >> goal_j;
        int cur, next;
        cur = pos(start_i, start_j, N);
        next = face == 'N' ? cur-4*row+S : (face == 'S' ? cur+row*4+N : (face == 'E' ? cur+4+W : cur-4+E));
        cur += face == 'N' ? S : (face == 'E' ? W : (face == 'S' ? N : W));
        adjList[cur].push_back(next);
        start = next;
        goal = pos(goal_i, goal_j, N);
        int i, j;
        while(cin >> i && i)
        {
            cin >> j;
            string str; // 每個點往哪個方向要往哪走的資訊
            while(cin >> str && str != "*")
            {
                for(int k = 1; k < str.size(); k++)
                {
                    cur = pos(i, j, N); // cur在(i, j)位置
                    if(str[0] == 'N') // 朝著N
                    {
                        if(str[k] == 'F') next = cur - row*4 + S;
                        else if(str[k] == 'R') next = cur + 4 + W;
                        else /*if(str[i] == 'L')*/ next = cur - 4 + E;
                    }
                    else if(str[0] == 'E') // 朝著E
                    {
                        if(str[k] == 'F') next = cur + 4 + W;
                        else if(str[k] == 'R') next = cur + row*4 + N;
                        else /*if(str[i] == 'L')*/ next = cur - row*4 + S;
                    }
                    else if(str[0] == 'S') // 朝著S
                    {
                        if(str[k] == 'F') next = cur + row*4 + N;
                        else if(str[k] == 'R') next = cur - 4 + E;
                        else /*if(str[i] == 'L')*/ next = cur + 4 + W;
                    }
                    else //if(str[0] == 'W') // 朝著W
                    {
                        if(str[k] == 'F') next = cur - 4 + E;
                        else if(str[k] == 'R') next = cur - row*4 + S;
                        else /*if(str[i] == 'L')*/ next = cur + row*4 + N;
                    }
                    cur += str[0] == 'S' ? N:(str[0] == 'W' ? E : (str[0] == 'N' ? S:W));
                    adjList[cur].push_back(next);
                }
            }
        }
        BFS bfs(adjList);
        bool startEqualGoal = false;
        vector<int> ans;
        for(int i = 0; i < 4; i++)
        {
            bfs.findShortestPath(start, goal+i);
            if(bfs.shortestPath.size() > 1)
            {
                if(ans.size() > bfs.shortestPath.size() || ans.size() == 0)
                {
                    ans = bfs.shortestPath;
                }
            }
            if(start == goal+i)
            {
                ans = bfs.shortestPath;
                break;
            }
        }
        cout << mazeName << endl;
        if(ans.size())
        {
            cout << "  " << "(" << start_i << "," << start_j << ")";
            for(int i = ans.size()-1, j = 2; i >= 0; i--, j++)
            {
                cout << " (" << ans[i]/4/row+1 << "," << (ans[i]/4)%row+1 << ")";
                if(j % 10 == 0 && i)
                {
                    cout << "\n";
                    if(i) cout << " ";
                }
            }
            cout << endl;
        }
        else
        {
            cout << "  No Solution Possible" << endl;
        }
        cin.get();
    }
    return 0;
}
==============================
測資：
input.txt
output.txt