UVa824 - Coast Tracker(實作)

題目大意：

我們寫 GPS 的一小部分功能，給予一張圖，地圖上只有陸地與海，我們只能走陸地且要沿著海岸線走，我們透過逆時鐘方向進行搜尋，找出下一個節點是我們可以走的方向，輸出下一個節點可以走的方向位置

方向位置圖如下:

需要注意的是，我們是根據上一個節點的方向開始逆時鐘，而不是每次都是從上一張圖的 1 開始。
　座標則是像我們畫方程式的座標相同，也就是北(x,y+1)，左上(-1,1)…以此類推，與平常不同。

分析

這題的邏輯跟我腦袋想的不太一樣啊…，讓我腦袋打結了QQ，我好笨。

這題有個地方比較酷，他是給你當前的方向，但你不可以直接使用當前方向直接進行逆時鐘搜尋，看下面的圖

你會發現，他的搜尋方向是 1，是因為他的上一個位置是 6，再來透過逆時鐘搜尋 7,0 都是海洋所以不可以往那方向走，但是 1 就是陸地所以可以往那方向走，所以搜尋位置就要從反向的位置 +1，來進行搜尋。

也就是上上面那張圖誤導了大家wwww，或是英文變不好QQ。

這裡我有用一個比較特別的寫法是我將陸地變成 1，海洋變成 2，這樣再透過 map 實作時會更加方便些，然後要記住上一個位置一定會是陸地，但這題是可以往回走的(不過是最後一個選擇)，需要特別注意。

心得

這題好吃 2D 邏輯與方向感，在我不願意透過紙筆來輔助時則發現我常常將一樣的邏輯重複思考，有點笨欸www，需要將英文再複習，我也透過了這題目將 2D 的邏輯與方向感變好，感覺好棒，學了好多東西呢，也要在將邏輯弄得夠清晰。
ε٩(๑> ₃ <)۶з。

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define pos 8
using namespace std;
int direct[pos][2] = {{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}} ;
int counter_direct[] = {4,5,6,7,0,1,2,3} ;
map<pair<int,int>,int> record;
int x , y , d , a , b , c ;

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    //freopen("out.txt" , "w" , stdout );
#endif // LOCAL
    while(cin >> x >> y >> d && x != -1){
        record.clear();
        for(int i = 0 ; i < pos ; i++){
            cin >> a >> b >> c ;
            record[make_pair(a,b)] = c ;
        }
        int ox , oy , r ;
        ox = x ; oy = y ;
        r = counter_direct[d];
        //record[make_pair(x+direct[r][0],y+direct[r][1])] = 0;
        //cout << "r is " << x+direct[r][0] << ' ' << y+direct[r][1] << '\n' ;
        for(int i = 1 ; i <= pos ; i++){
            d = (r+i) % 8 ;
            //cout << "r is " << r << '\n' ;
            x = ox + direct[d][0] ;
            y = oy + direct[d][1] ;
            //cout << x << ' ' << y << '\n' ;
            if(record[make_pair(x,y)] == 1 ){
                cout << d << '\n' ;
                break ;
            }
        }

    }

    return 0;
}